php中实现二分法查找的程序代码
发布:smiling 来源: PHP粉丝网 添加日期:2016-08-30 14:22:30 浏览: 评论:0
二分法查找在高级点的开发可能会用到了,当然在大公司找工作时都会有面试题是这种了,下面我们来看一篇关于二分法查找在php中实现方法,具体的细节如下所示.
二分法(dichotomie) 即一分为二的方法,设[a,b]为R的闭区间,逐次二分法就是造出如下的区间序列([an,bn]):a0=a,b0=b,且对任一自然数n,[an+1,bn+1]或者等于[an,cn],或者等于[cn,bn],其中cn表示[an,bn]的中点.
例子1:
- header('Content-Type: text/html; charset=utf-8;');
- $arr = array(2,33,22,1,323,321,28,36,90,123);
- sort($arr);
- //二分法查找
- echo $index = binarySearch($arr,321);
- function binarySearch($arr,$key){
- $len = count($arr);
- $mid = -1;
- $start = 0;
- $end = $len-1;
- while($start<=$end){
- $mid = (int)(($start+$end)/2);
- echo $mid."\n";
- if($arr[$mid] == $key){
- return $mid;
- }else if($arr[$mid] < $key){
- $start = $mid+1;
- }else if($arr[$mid] > $key){
- $end = $mid-1;
- }
- }
- }
例子2:
- <?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);
- } //phpfensi.com
- else
- {
- return search($array, $k, $mid+1, $high);
- }
- }
- return -1;
- }
- $array = array(4,5,7,8,9,10); //测试search函数
- echo search($array, 8); //调用search函数并输出查找结果
- ?>
Tags: php二分法 php查找程序
- 上一篇:php实现上一篇下一篇的方法总结
- 下一篇:php结合mysql查询无限下级树输出
推荐文章
热门文章
最新评论文章
- 写给考虑创业的年轻程序员(10)
- PHP新手上路(一)(7)
- 惹恼程序员的十件事(5)
- PHP邮件发送例子,已测试成功(5)
- 致初学者:PHP比ASP优秀的七个理由(4)
- PHP会被淘汰吗?(4)
- PHP新手上路(四)(4)
- 如何去学习PHP?(2)
- 简单入门级php分页代码(2)
- php中邮箱email 电话等格式的验证(2)