PHP二分法查找算法原理和代码实现

blogdaren 2014-09-28 抢沙发 2891人次

二分法查找算法原理:

当数据量很大时适宜采用该方法,采用二分法查找时,前提条件是数据必须是排好序的,其主要思想是:

(设查找的数组区间为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)。

PHP实现代码:

<?php
//search函数 其中$array为数组,$k为要找的值,$low为查找范围的最小键值,$high为查找范围的最大键值
function search($array, $k, $low=0, $high=0)    
{ 
    if(count($array)!=0 and $high == 0)                 //判断是否为第一次调用
    {
        $high = count($array);
    }

    if($low <= $high)                                   //如果还存在剩余的数组元素
    { 
        $mid = intval(($low+$high)/2);                  //取$low和$high的中间值
        if ($array[$mid] == $k)                         //如果找到则返回
        { 
            return $mid; 
        }
        elseif ($k < $array[$mid])                      //如果没有找到,则继续查找
        { 
            return search($array, $k, $low, $mid-1); 
        }
        else
        { 
            return search($array, $k, $mid+1, $high); 
        } 
    } 
    return -1; 
} 

$array = array(4,5,7,8,9,10);                           //测试search函数
echo search($array, 8);                                 //调用search函数并输出查找结果

#二分法查找算法原理#

版权声明:除非注明,本文由( blogdaren )原创,转载请保留文章出处。

本文链接:PHP二分法查找算法原理和代码实现

发表评论:

您的昵称:
电子邮件:
个人主页:

Free Web Hosting