常见查找算法之php, js,python版
常用算法
>>>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));// 3
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)) # 3
print(search(data,'7')) # False
print(search(data,6)) # 5
>>>
1. 用low , high , middle 表示待查找区间的 下界, 上界,中间 的坐标
2. 取中间位置 middle = floor((low+high)/2)
大于: 待查数据在区间的后半段 设low 为 middle+1
小于: 待查数据在区间的前半段 设high 为 middle-1
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)); // 6
print_r(bisearch($data_list,5)); // 3
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)); # 6
print(bisearch(data_list,5)); # 3
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)); // 6
console.log(bisearch(data_list,5)); // 3
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版
$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)); // 6
print(interpolation($data_list,5)); // 3
print(interpolation($data_list,13)); // false
$index = interpolation($data_list,10);
echo $data_list[$index];// 10
/*
注: 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)); # 6
print(interpolation(data_list,5)); # 3
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)); // 6
console.log(interpolation(data_list,5)); // 3
console.log(interpolation(data_list,13)); // False
截图:
小结: