首页 后端开发 php教程 浅谈PHP第三弹---使用二分查找法查找数组中的元素位置_PHP教程

浅谈PHP第三弹---使用二分查找法查找数组中的元素位置_PHP教程

Jul 13, 2016 pm 05:50 PM
array php 位置 使用 元素 我们 数组 查找

在php中我们可以通过array_search()函数来查找一个数组内的元素值的键名.

同样,我们可以通过使用二分法来查找数组内的元素的键名.
那什么是二分法呢?

我来解释下:
如果数据是按升序排序的,我们从数据的中间位置开始查找,若给定的值恰好等于当前位置的值,查找成功,若给定的值小于当前位置的值,那我们就从以当前值为准查找其前半部分的值,反之,若给定的值大于当前值,那么就从以当前值为准查找其后半部分的值.

也就是说,利用二分法查找的数据,必须是排好序的.
下面我们尝试查找数组array(1,2,3,4,5,6,7,8,9,10)中的某一个值的位置:
function Search($a,$val){
$low = 0;
$high= count($a) - 1;
while($low $mid = intval(($low+$high)/2);
if($a[$mid] == $val)
return $mid;
if($a[$mid] > $val){
$high = $mid - 1;
}else{
$low = $mid + 1;
}
}
return -1;
}
?>
以上函数,第一个参数为传入的数组,第二个参数为该数组需要查询的值.
我们给数组的键设置一个最小值$low为0,设置一个最大值为$high为数组长度减一,那么中间值我们就可以设置为intval(($low+$height)/2),
也就是说,当数组元素长度为奇数时,数组的中间值正好在正中间,
例如数组长度为5,那中间值正好为2,也就是(0+4)/2,
0,1,2,3,4
那当我们的数组长度为偶数时,利用上述公式是无法除尽的,所以我们要取整,无论是进一法取整还是舍去法取整都是可以的
例如数组长度为6,那中间值为(0+5)/2,值为2.5,那数组中键为2.5的是不存在的,所以我们就需要取整为2
0,1,2,3,4,5
如果使用上述取整函数intval或者是floor函数获得的键为2,如果使用ceil取整,这里得到的键即为3

那么,我们拿上面的数组来说:
数组的长度为10,那么中间值即为intval((0+(10-1))/2),为4,索引为4的也就是数组中的第五个元素"5"
1,2,3,4,5,6,7,8,9,10

好,我们下面开始判断,
1.如果需要查询的值恰好为"5",查找成功,直接返回该值的索引即可.
也就是
if($a[$mid] == $val)
return $mid;
2.如果要查询的值小于"5",我们需要把$high的值设为中间值减一,即为4-1,并返回继续查询中间值的前半部分(红色部分)
1,2,3,4,5,6,7,8,9,10
即为:
if($a[$mid] > $val){
$high = $mid - 1;
}

3.如果要查询的值大于"5",我们就需要把$low的值设为中间值加一,即为4+1,并返回继续查询中间值的后半部分(红色部分)
1,2,3,4,5,6,7,8,9,10
即为:
else{
$low = $mid + 1;
}
设置完之后,返回继续查询,如果满足条件$low while($low .......
}
return -1;
此函数的缺点在于:
如果数组中有重复的值,只能查到其中的一个值的键,有兴趣的童鞋,可以对以上函数进行完善,跟帖回复.

 

摘自 zdrjlamp

www.bkjia.comtruehttp://www.bkjia.com/PHPjc/478286.htmlTechArticle在php中我们可以通过array_search()函数来查找一个数组内的元素值的键名. 同样,我们可以通过使用二分法来查找数组内的元素的键名. 那什么是...
本站声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

AI Hentai Generator

AI Hentai Generator

免费生成ai无尽的。

热门文章

R.E.P.O.能量晶体解释及其做什么(黄色晶体)
2 周前 By 尊渡假赌尊渡假赌尊渡假赌
仓库:如何复兴队友
1 个月前 By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island冒险:如何获得巨型种子
4 周前 By 尊渡假赌尊渡假赌尊渡假赌

热工具

记事本++7.3.1

记事本++7.3.1

好用且免费的代码编辑器

SublimeText3汉化版

SublimeText3汉化版

中文版,非常好用

禅工作室 13.0.1

禅工作室 13.0.1

功能强大的PHP集成开发环境

Dreamweaver CS6

Dreamweaver CS6

视觉化网页开发工具

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

CakePHP 项目配置 CakePHP 项目配置 Sep 10, 2024 pm 05:25 PM

在本章中,我们将了解CakePHP中的环境变量、常规配置、数据库配置和电子邮件配置。

适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 适用于 Ubuntu 和 Debian 的 PHP 8.4 安装和升级指南 Dec 24, 2024 pm 04:42 PM

PHP 8.4 带来了多项新功能、安全性改进和性能改进,同时弃用和删除了大量功能。 本指南介绍了如何在 Ubuntu、Debian 或其衍生版本上安装 PHP 8.4 或升级到 PHP 8.4

CakePHP 日期和时间 CakePHP 日期和时间 Sep 10, 2024 pm 05:27 PM

为了在 cakephp4 中处理日期和时间,我们将使用可用的 FrozenTime 类。

CakePHP 文件上传 CakePHP 文件上传 Sep 10, 2024 pm 05:27 PM

为了进行文件上传,我们将使用表单助手。这是文件上传的示例。

CakePHP 路由 CakePHP 路由 Sep 10, 2024 pm 05:25 PM

在本章中,我们将学习以下与路由相关的主题?

讨论 CakePHP 讨论 CakePHP Sep 10, 2024 pm 05:28 PM

CakePHP 是 PHP 的开源框架。它的目的是使应用程序的开发、部署和维护变得更加容易。 CakePHP 基于类似 MVC 的架构,功能强大且易于掌握。模型、视图和控制器 gu

如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 如何设置 Visual Studio Code (VS Code) 进行 PHP 开发 Dec 20, 2024 am 11:31 AM

Visual Studio Code,也称为 VS Code,是一个免费的源代码编辑器 - 或集成开发环境 (IDE) - 可用于所有主要操作系统。 VS Code 拥有针对多种编程语言的大量扩展,可以轻松编写

CakePHP 创建验证器 CakePHP 创建验证器 Sep 10, 2024 pm 05:26 PM

可以通过在控制器中添加以下两行来创建验证器。

See all articles