二分查找

二分查找

二分查找

二分查找,针对的是一个有序的数据集合(这点很重要)。
每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。

注意到二分查找针对的必须是已经排序过的有序数组,否则不能使用该算法。

二分查找的公式

undefined

二分查找代码

function binary_search($nums, $num)
{
if (count($nums) <= 1) {
return 0;
}
return binary_search_internal($nums, $num, 0, count($nums) - 1);
}

function binary_search_internal($nums, $num, $low, $high)
{
if ($low > $high) {
return -1;
}

$mid = floor(($low + $high) / 2);
if ($num > $nums[$mid]) {
return binary_search_internal($nums, $num, $mid + 1, $high);
} elseif ($num < $nums[$mid]) {
return binary_search_internal($nums, $num, $low, $mid - 1);
} else {
return $mid;
}
}

$nums = [1, 2, 3, 4, 5, 6];
$index = binary_search($nums, 5);
var_dump($index);

总结

二分查找的时间复杂度是 O(logn);
二分查找在线性表结构中的应用非常广泛。
但是使用二分查找需要注意一个前提,那就是针对有序数组,换言之,二分查找适用于变动不是很频繁的静态序列集,如果序列集变动很频繁,经常进行插入删除操作,那么就要不断维护这个序列集的排序,这个成本也很高,因此,这种情况下就不适用二分查找了,比如我们的数据库查询,增删改查很频繁,显然不是通过二分查找来进行查询的.

二分查找的变异

1.取出二叉树中重复的第一个或最后一个数据的下表

function binary_search($nums, $num)
{
if (count($nums) <= 1) {
return 0;
}
return binary_search_internal($nums, $num, 0, count($nums) - 1);
}

function binary_search_internal($nums, $num, $low, $high)
{
if ($low > $high) {
return -1;
}

$mid = floor(($low + $high) / 2);
if ($num < $nums[$mid]) {
return binary_search_internal($nums, $num, $low, $mid - 1);//-1是减去中间数.毕竟数组从0开始
} elseif ($num > $nums[$mid]) {
return binary_search_internal($nums, $num, $mid + 1, $high);//+1是因为要把中间数加上.
} else {
if ($mid == 0 || $nums[$mid-1] != $num) {
//现在是取得第一个重复的.
//$mid == count($nums) - 1 || $nums[$mid + 1] != $num是取得最后一个重复的.
return $mid;
} else {
return binary_search_internal($nums, $num, $low, $mid - 1);
}
}
}

$nums = [1, 1, 3, 3, 4, 4, 6];
$index = binary_search($nums, 4);
var_dump($index);

2.查找第一个大于等于给定值的元素(省略了通用的代码binary_search)

function binary_search_internal($nums, $num, $low, $high)
{
if ($low > $high) {
return -1;
}

$mid = floor(($low + $high) / 2);
if ($num <= $nums[$mid]) {
if ($mid == 0 || $nums[$mid - 1] < $num) {
return $mid;
} else {
return binary_search_internal($nums, $num, $low, $mid - 1);
}
} elseif ($num > $nums[$mid]) {
return binary_search_internal($nums, $num, $mid + 1, $high);
}
}

$nums = [1, 2, 3, 5, 6,7];
$index = binary_search($nums, 4);
print $index;

3.查找最后一个小于等于给定值的元素

function binary_search_internal($nums, $num, $low, $high)
{
if ($low > $high) {
return -1;
}

$mid = floor(($low + $high) / 2);
if ($num >= $nums[$mid]) {
if ($mid == count($nums) - 1 || $nums[$mid + 1] > $num) {
return $mid;
} else {
return binary_search_internal($nums, $num, $mid + 1, $high);
}
} elseif ($num < $nums[$mid]) {
return binary_search_internal($nums, $num, $low, $mid - 1);
}
}

$nums = [1, 2, 3, 5, 6,7];
$index = binary_search($nums, 4);
print $index;

4.插值查找

插值查找,有序表的一种查找方式。
插值查找是根据查找关键子与查找表中最大最小记录关键字比较后的查找方法。
插值查找基于二分查找,将查找点的选择改进为自适应选择,提高查找效率。
插值查找不适用于波动较大的数组中.

插值查找的算法

undefined

插值查找的代码

function insertsearch($arr,$num){
$count = count($arr);
$lower = 0;
$high = $count - 1;
while($lower <= $high){
if($arr[$lower] == $num){
return $lower;
}
if($arr[$high] == $num){
return $high;
}

//这里是插值查找的 核心算法
$middle = intval($lower + ($num - $arr[$lower]) / ($arr[$high] - $arr[$lower]) * ($high - $lower));
if($num < $arr[$middle]){
$high = $middle - 1;
}else if($num > $arr[$middle]){
$lower = $middle + 1;
}else{
return $middle;
}
}
return -1;
}
$arr = array(0,1,16,25,25,47,59,62,73,88,99);
$pos = insertsearch($arr,25);
print($pos);

5.斐波那契数列

斐波那契数列指的是这样一个数列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377,610,987,1597,2584,4181,6765,10946,17711,28657,46368........

这个数列从第3项开始,每一项都等于前两项之和。

F0=0,F1=1,Fn=F(n-1)+F(n-2)

代码

function fib($n){
$array = array();
$array[0] = 1;
$array[1] = 1;
for($i=2;$i<$n;$i++){
$array[$i] = $array[$i-1]+$array[$i-2];
}
return $array;
}
var_dump(fib(10));