1、简介
当数据量很大适宜采用该方法。采用二分法查找时,数据需是排好序的。主要思想是:(设查找的数组区间为array[low, high])(1)确

定该期间的中间位置K(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下

:a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]b.array[k]<T 类似上面查找区间为array

[k+1,……,high]。每一次查找与中间值比较,可以确定是否查找成功,不成功当前查找区间缩小一半。递归找,即可,时间复杂度:O(log2n)。

2、算法
假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.
1.开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为mid>x,故应在前半段中查找。
2.令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>mid,故确定应在后半段中查找。
3.令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。
如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。
例:在有序的有N个元素的数组中查找用户输进去的数据x。
算法如下:
1.确定查找范围front=0,end=N-1,计算中项mid=(front+end)/2。
2.若a[mid]=x或front>=end,则结束查找;否则,向下继续。
3.若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内,则把mid+1的值赋给front,并重新计算mid,转去执行步骤2;若a[mid]>x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。
[一维数组,折半查找]

3.1 时间复杂度
1.最坏情况查找最后一个元素(或者第一个元素)Master定理T(n)=T(n/2)+O(1)所以T(n)=O(logn)
2.最好情况查找中间元素O(1)查找的元素即为中间元素(奇数长度数列的正中间,偶数长度数列的中间靠左的元素)

3.2 空间复杂度
S(n)=n

4、PHP示例代码

<?php
function binarySearch($array, $val) {
$count = count($array);
$low = 0;
$high = $count – 1;
while ($low <= $high) {
$mid = intval(($low + $high) / 2);
if ($array[$mid] == $val) {
return $mid;
}
if ($array[$mid] < $val) {
$low = $mid + 1;
} else {
$high = $mid – 1;
}
}
return false;
}

5、PHP二分法查找数据
对已经排好的数据进行查找

<?php
$array = array(1,6,9,10,15,89,444,789,1000,1001,1566,1777,1899,1999,2000,2144,2589);

function binary_search($array, $start, $end, $find)
{
$mid = floor(($start + $end) / 2);

if ($array[$mid] == $find)
{
return $mid;
}

if ($array[$mid] > $find) //left
{
return binary_search($array, $start, $mid – 1, $find);
}
else
{
return binary_search($array, $mid + 1, $end, $find);
}
}
?>

<?php
//测试
foreach($array as $value)
{
$time = microtime(true);
binary_search($array, 0, count($array)-1, $value);
//in_array($value,$array);
printf(“%d-%0.5f\n”, $value,microtime(true)-$time);
}

//结果

PHP二分法查找数据

//in_array测试结果

PHP二分法查找数据

//////////非递归方式////////////

<?php
function binary_search($array, $find)
{
$start = 0;
$end   = count($array);

while($start <= $end)
{
$mid = floor(($start+$end) / 2);

if ($array[$mid] == $find)
{
return $mid;
}

if ($array[$mid] > $find) //left
{
$end = $mid – 1;
}
else
{
$start = $mid + 1;
}
}
}

////////////执行结果///////////////////

PHP二分法查找数据