问题:对于一列有序数组,如何判断给出的一个值,该值是否存在于数组。
思路:判断是否存在,最简单是,直接循环该数组,对每一个值进行比较。但是对于有序数组来说,这样写就完全没有利用好“有序”这一特点。
所有我们使用到“二分法查找”,
//有序数组为 $arr = array(2,5,66,87,954,1452,5865); //查找值 $str = 1452; //我们先定义 三个参数 $front = 0;//一个开始值下标 $end = count($arr) - 1;//一个结束值下标 $mid = intval(($front + $end) / 2);//中间值下标
1、第一次比较,我们直接判断查找值str是否等于中间值mid,如果等于 直接返回 true;
2、如果查找值str大于中间值mid,则说明查找值str可能在中间值的右边,即对开始值front需重新赋值 = 中间值mid + 1,结束值end不用变,依次中间值mid为新的开始值 + 结束值;
3、如果查找值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
int(3)
以上就是PHP查找一列有序数组是否包含某值(二分查找)的详细内容,如果有任何补充可以联系站长技术小编。
2月5日消息 深度操作系统官方近期发布了 2020 年 deepin 回顾 ,2020 年,deepin...
原文始发于 https://mp.weixin.qq.com/s/UIL5Mt661WbPYtlF1byxCg 前言 在鹅厂实...
本文实例讲述了JSP使用Servlet作为控制器实现MVC模式的方法。分享给大家供大家参...
使用 LVSKeepalived 实现 MySQL双主复制高可用 一、 部署 MySQL 双主复制 1.配置...
目录 基本语句 1 赋值 赋值运算符 : 或 2 单一行结果返回 SELECT...INTO 语法赋...
1 需要了解的知识点 1.1 offset(偏移量) 定义:元素在屏幕上占用的所有的可见...
说明:部分内容有待进一步研究和修正,因为最近工作太忙,暂时抽不出时间来,未...
根据TIOBE 编程语言排行榜前20的语言分享相关图书(部分空缺)。 在正式介绍编程...
json 在上篇文章已有详细介绍,json的既简单易懂,又传输迅速。并且能和javascri...
准备工作 一般分页查询 使用子查询优化 使用 id 限定优化 使用临时表优化 关于数...