常用算法
>>>1. 顺序查找, 也叫线性查找, 它从第一个记录开始, 挨个进行对比, 是最基本的查找技术
javaScript 版顺序查找算法:
// 顺序查找(线性查找) 只做找到即返回
// javaScript 版
function search(data,needle)
{
for(var i=0;i<data.length;i++)
{
if(data[i] == needle && typeof data[i] == typeof needle)
{
return i;
}
}
return false;
}
var data = [100,10,2,7,8,6];
console.log(search(data,7));//
console.log(search(data,'7'));// false
php版顺序查找算法:
<?php
// php版
function search($data,$needle)
{
$data_len = count($data);
for($i=0;$i<$data_len;$i++)
{
if($data[$i] === $needle) return $i;
}
return false;
}
$data = [100,10,2,7,8,6];
var_dump(search($data,7));// int(3)
var_dump(search($data,'7'));// bool(false)
python3 版顺序查找算法:
# python3 版本
def search(data,needle) :
dataLen = len(data)
for i in range(dataLen) :
if data[i] == needle and type(data[i]) == type(needle) : return i
return False
data = [100,10,2,7,8,6]
print(search(data,7)) #
print(search(data,'')) # False
print(search(data,6)) #
>>>二分找查, 折半查找
核心思想:
1. 用low , high , middle 表示待查找区间的 下界, 上界,中间 的坐标
2. 取中间位置 middle = floor((low+high)/2)
3. 用给定值与 中间位置的值 作比较
等于: 查找成功
大于: 待查数据在区间的后半段 设low 为 middle+1
小于: 待查数据在区间的前半段 设high 为 middle-1
4.数据是排序好的
5.直到越界 (low>high) 查找失败, 结束
PHP版二分查找算法:
<?php
// 二分法 折半查找 PHP版
$data_list = [1,2,4,5,5,6,10,12];
function bisearch($data_list,$needle)
{
$low = 0;
$high = count($data_list)-1;
if($data_list[$low] == $needle) return $low;
if($data_list[$high] == $needle) return $high;
while($high>=$low)
{
$middle = floor(($low+$high)/2);
if($needle == $data_list[$middle])
{
return $middle;
}elseif($needle>$data_list[$middle])
{
$low = $middle+1;
}else{
$high = $middle-1;
}
}
return false;
}
print_r(bisearch($data_list,10)); //
print_r(bisearch($data_list,5)); //
print_r(bisearch($data_list,13)); // false
python 3版 二分查找算法:
import math
# python3 版二分查找算法
def bisearch(data_list,needle) :
low,high = 0,len(data_list)-1
if needle == data_list[low] : return low
if needle == data_list[high] : return high
while high>=low :
middle = math.floor((high+low)/2)
if needle == data_list[middle] : return middle
elif needle > data_list[middle] : low = middle+1
else : high = middle-1
return False
data_list = [1,2,4,5,5,6,10,12]
print(bisearch(data_list,10)); #
print(bisearch(data_list,5)); #
print(bisearch(data_list,13)); # False
javaScript 版二分查找算法:
// js 版二分查找
function bisearch(data_list,needle)
{
var low = 0,high = data_list.length-1
if (needle == data_list[low] ) return low
if (needle == data_list[high]) return high
while (high>=low)
{
var middle = Math.floor((low+high)/2)
if(needle == data_list[middle])
{
return middle
}else if(needle>data_list[middle])
{
low = middle + 1
}else{
high = middle - 1
}
}
return false
}
data_list = [1,2,4,5,5,6,10,12]
console.log(bisearch(data_list,10)); //
console.log(bisearch(data_list,5)); //
console.log(bisearch(data_list,13)); // False
>>> 插值查找 (由二分查找改进)
二分查找的公式:
middle = (low+high)/2 => low+(1/2)*(high-low)
插值查找的公式由上面演变, 主要改进的是二分之一部分:
middle = low+((needle-data[low])/(data[high]-data[low]))*(high-low)
对二分查找跟插值查找的一个说明:
插值查找对于公布均匀的数据, 速度比二分查找快(插值查找次数少),例如对下面这类数据
$data = [1,2,3,6,7,9,10,11,...]
对于分布不均匀的数据, 二分查找要比插值查找快 例如下:
$data = [4,100,300,685,3452,...]
PHP版 插值查找算法:
<?php
// 二分查找优化(插值查找) PHP版
$data_list = [1,2,4,5,5,6,10,12];
function interpolation($data_list,$needle)
{
$low = 0;
$high = count($data_list)-1;
if($data_list[$low] == $needle) return $low;
if($data_list[$high] == $needle) return $high;
while($high>=$low)
{
$middle = floor($low+(($needle-$data_list[$low])/($data_list[$high]-$data_list[$low]))*($high-$low));
if($needle == $data_list[$middle])
{
return $middle;
}elseif($needle>$data_list[$middle])
{
$low = $middle+1;
}else{
$high = $middle-1;
}
}
return false;
}
print(interpolation($data_list,10)); //
print(interpolation($data_list,5)); //
print(interpolation($data_list,13)); // false
$index = interpolation($data_list,10);
echo $data_list[$index];//
/*
注: 1.floor 返回的是浮点数 如 6 类型为float
2.false 用print,echo 输出是空字符串
*/
python3版 插值查找算法:
import math
# python3 插值查找算法
def interpolation(data_list,needle) :
low,high = 0,len(data_list)-1
if needle == data_list[low] : return low
if needle == data_list[high] : return high
while high>=low :
middle = math.floor(
low+
((needle-data_list[low])/(data_list[high]-data_list[low]))*
(high-low)
)
if needle == data_list[middle] : return middle
elif needle > data_list[middle] : low = middle+1
else : high = middle-1
return False
data_list = [1,2,4,5,5,6,10,12]
print(interpolation(data_list,10)); #
print(interpolation(data_list,5)); #
print(interpolation(data_list,13)); # False
js 版插值查找算法:
// js版 插值查找算法
function interpolation(data_list,needle)
{
var low = 0,high = data_list.length-1
if (needle == data_list[low] ) return low
if (needle == data_list[high]) return high
while (high>=low)
{
var middle = Math.floor(
low+((needle-data_list[low])/(data_list[high]-data_list[low]))*
(high-low)
)
if(needle == data_list[middle])
{
return middle
}else if(needle>data_list[middle])
{
low = middle + 1
}else{
high = middle - 1
}
}
return false
}
data_list = [1,2,4,5,5,6,10,12]
console.log(interpolation(data_list,10)); //
console.log(interpolation(data_list,5)); //
console.log(interpolation(data_list,13)); // False
小结:
以上有php,python,js 版常见的查找算法:
1. 顺序(线性) 查找
2. 二分查找 (折半查找)
3. 插值查找 (二分查找优化 适用于分布均匀的数据)
4. 前提是数据排好序, 顺序