成绩:关于一列有序数组,若何判别给出的一个值,该值能否存正在于数组。
思绪:判别能否存正在,最简略是,间接轮回该数组,对每个值进行比拟。然而关于有序数组来讲,这样写就齐全不行使好“有序”这一特性。
一切咱们应用到“二分法查找”,
//有序数组为 $arr = array(2,5,66,87,954,1452,5865); //查找值 $str = 1452; //咱们先界说 三个参数 $front = 0;//一个开端值下标 $end = count($arr) - 1;//一个完结值下标 $mid = intval(($front + $end) / 2);//两头值下标
一、第一次比拟,咱们间接判别查找值str能否等于两头值mid,假如等于 间接前往 true;
二、假如查找值str年夜于两头值mid,则阐明查找值str可能正在两头值的左边,即对开端值front需从新赋值 = 两头值mid + 1,完结值end不必变,顺次两头值mid为新的开端值 + 完结值;
三、假如查找值str小于两头值mid,则阐明查找值str可能正在两头值的右边,即开端值不必变,完结值end需从新赋值 = 两头值 - 1,顺次两头值mid为开端值 + 新的完结值;
-----如上,关于传入的开端值,完结值,两头值,进行比拟。一旦开端值 年夜于 完结值 则阐明不找到,完结查问,反之等于就前往已找到。
详细代码以下:
$str = 89;//查找值 $arr = [1,55,66,89,420];//有序数组 $ren = find($arr, $str); echo '<pre>'; var_dump($ren); function find($arr, $str){ $front = 0;//开端下标 $end = count($arr) - 1;//完结下标 while($front <= $end){//完结值 年夜于 开端值 ,反之则加入 $mid = intval(($front + $end) / 2);//两头值下标 if($str == $arr[$mid]){ return $mid;//存正在间接前往值的下标 } if($str > $arr[$mid]){ $front = $mid + 1;//正在后面 } if($str < $arr[$mid]){ $end = $mid - 1;//正在前面 } } return false; }
前往后果:89为第四个元素值下标3
保举视频教程:《php教程》
以上就是PHP查找一列有序数组能否蕴含某值(二分查找)的具体内容,更多请存眷资源魔其它相干文章!
标签: php php开发教程 php开发资料 php开发自学
版权声明:除非特别标注,否则均为本站原创文章,转载时请以链接形式注明文章出处。
抱歉,评论功能暂时关闭!