PHP算法之二分查找

page_img_url

二分查找的定义

二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。

算法的要求

从上面的定义我们可以知道,满足该算法的要求必须如下两点:

  • 必须采用顺序存储结构。
  • 必须按关键字大小有序排列。

算法的步骤

其实,二分查找也还是比较容易理解的,大概就是一分为二,然后两边比较,保留有效区间,继续一分为二查找,直到找到或者超出区间则结束,所以二分查找的基本步骤是:

  • 确定要查找的区间
  • 确定要二分时的参照点
  • 区间内选取二分点
  • 根据二分点的值,综合左右区间情况以及求解的目的,舍去一半无用的区间
  • 继续在有效区间重复上面的步骤

算法源码

这里,我主要采用递归和非递归两种方法实现,具体如下:

首先第一种是非递归的算法实现,算法如下:

  1. /**
  2. * 二分查找算法
  3. * @param array $arr 待查找区间
  4. * @param int $number 查找数
  5. * @return int 返回找到的键
  6. **/
  7. function binary_search($arr, $number) {
  8. // 非数组或者数组为空,直接返回-1
  9. if (!is_array($arr) || empty($arr)) {
  10. return -1;
  11. }
  12. // 初始变量值
  13. $len = count($arr);
  14. $lower = 0;
  15. $high = $len - 1;
  16. // 最低点比最高点大就退出
  17. while ($lower <= $high) {
  18. // 以中间点作为参照点比较
  19. $middle = intval(($lower + $high) / 2);
  20. if ($arr[$middle] > $number) {
  21. // 查找数比参照点小,舍去右边
  22. $high = $middle - 1;
  23. } else if ($arr[$middle] < $number) {
  24. // 查找数比参照点大,舍去左边
  25. $lower = $middle + 1;
  26. } else {
  27. // 查找数与参照点相等,则找到返回
  28. return $middle;
  29. }
  30. }
  31. // 未找到,返回-1
  32. return -1;
  33. }

然后第二种是递归的算法实现,算法如下:

  1. /**
  2. * @param array $arr 待查找区间
  3. * @param int $number 查找数
  4. * @param int $lower 区间最低点
  5. * @param int $high 区间最高点
  6. * @return int
  7. **/
  8. function binary_search_recursion(&$arr, $number, $lower, $high) {
  9. // 以区间的中间点作为参照点比较
  10. $middle = intval(($lower + $high) / 2);
  11. // 最低点比最高点大就退出
  12. if ($lower > $high) {
  13. return -1;
  14. }
  15. if ($number > $arr[$middle]) {
  16. // 查找数比参照点大,舍去左边继续查找
  17. return binary_search_recursion($arr, $number, $middle + 1, $high);
  18. } elseif ($number < $arr[$middle]) {
  19. // 查找数比参照点小,舍去右边继续查找
  20. return binary_search_recursion($arr, $number, $lower, $middle - 1);
  21. } else {
  22. return $middle;
  23. }
  24. }

算法的使用

需求是在一个排列好的区间($arr)中,查找一个数($number)的所在位置,所以,调用算法查找如下:

  1. // 待查找区间
  2. $arr = [1, 3, 7, 9, 11, 57, 63, 99];
  3. // 非递归查找57所在的位置
  4. $find_key = binary_search($arr, 57);
  5. // 递归查找57所在的位置
  6. $find_key_r = binary_search_recursion($arr, 57, 0, count($arr));
  7. // 输出打印
  8. print_r($find_key);
  9. print_r($find_key_r);

时间复杂度分析

在有序数组中如果用暴力的算法去查找,也就是逐个遍历比较,那么时间复杂度是O(n);但是,用二分查找后,因为每次可以舍去一半查找区间,所以会将时间复杂度减少到O(logn),算法更优。