【二分查找】
二分查找针对的是一个有序的数据集合，查找思想有点类似分治思想。每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。
二分查找是一种非常高效的查找算法，时间复杂度是 O(logn)。O(logn) 这种对数时间复杂度，是一种极其高效的时间复杂度，有的时候甚至比时间复杂度是常量级O(1) 的算法还要高效。二分查找更适合处理静态数据，也就是没有频繁的数据插入、删除操作。
使用循环和递归都可以实现二分查找。
二分查找应用场景的局限性：
- 二分查找依赖的是顺序表结构，简单点说就是数组。（链表不可以）
- 二分查找针对的是有序数据。（如果数据没有序，我们需要先排序。）
- 数据量太大不适合二分查找。
四种常见的二分查找变形问题
1.查找第一个值等于给定值的元素
2.查找最后一个值等于给定值的元素
3.查找第一个大于等于给定值的元素
4.查找最后一个小于等于给定值的元素
适用性分析
1.凡事能用二分查找解决的，绝大部分我们更倾向于用散列表或者二叉查找树，即便二分查找在内存上更节省，但是毕竟内存如此紧缺的情况并不多。
2.求“值等于给定值”的二分查找确实不怎么用到，二分查找更适合用在”近似“查找问题上。比如上面讲几种变体。
<?php /** * 二分查找 查找=find的元素 * @param array $numbers * @param [type] $find */ function binarySearch(array $numbers, $find) { $low = 0; $high = count($numbers) - 1; return search($numbers, $low, $high, $find); } function search(array $numbers, $low, $high, $find) { /** * notice1 循环退出条件 */ if ($low > $high) { return -1; } /** * notice2 mid计算 */ $mid = $low + (($high - $low) >> 1); if ($numbers[$mid] > $find) { //notice3 high值更新 return search($numbers, $low, $mid - 1, $find); } elseif ($numbers[$mid] < $find) { //notice4 low值更新 return search($numbers, $mid + 1, $high, $find); } else { return $mid; } } /** * 求数字的平方根，保留6位小数 * @param [type] $number */ function squareRoot($number) { if ($number < 0) { return -1; } elseif ($number < 1) { $min = $number; $max = 1; } else { $min = 1; $max = $number; } $mid = $min + ($max - $min) / 2; while (getDecimalPlaces($mid) < 6) { $square = $mid * $mid; if ($square > $number) { $max = $mid; } elseif ($square == $number) { return $mid; } else { $min = $mid; } $mid = $min + ($max - $min) / 2; } return $mid; } /** * 计算数字小数点后有几位数字 * @param [type] $number */ function getDecimalPlaces($number) { $temp = explode('.', $number); return @strlen($temp[1]); } // 测试二分查找给定值 $numbers = [0, 1, 2, 3, 3, 4, 5, 6, 7, 9]; $find = 6; echo binarySearch($numbers, $find); echo " "; //测试求平方根 echo squareRoot(3); echo " ";
<?php /** * 找到第一个=value的元素 * @param array $numbers */ function findFirstEqual(array $numbers, $find) { $length = count($numbers); $low = 0; $high = $length - 1; while ($low <= $high) { $mid = $low + (($high - $low) >> 1); if ($numbers[$mid] > $find) { $high = $mid - 1; } else if ($numbers[$mid] < $find) { $low = $mid + 1; } else { /** * 如果是第一个元素，或之前一个元素不等于我们要找的值 * 我们就找到了第一个=find的element */ if ($mid == 0 || $numbers[$mid - 1] != $find) { return $mid; } else { $high = $mid - 1; } } } return -1; } /** * 找到最后一个=find的元素 * @param array $numbers * @param [type] $find */ function findLastEqual(array $numbers, $find) { $length = count($numbers); $low = 0; $high = $length - 1; while ($low <= $high) { $mid = $low + (($high - $low) >> 1); if ($numbers[$mid] > $find) { $high = $mid - 1; } else if ($numbers[$mid] < $find) { $low = $mid + 1; } else { /** * 如果mid是最后一个元素的index * 或mid后一个元素!=我们要找的值 * 则找到了最后一个=find的value */ if ($mid == $length - 1 || $numbers[$mid + 1] != $find) { return $mid; } else { $low = $mid + 1; } } } return -1; } /** * 找到第一个大于等于find的元素 * @param array $numbers * @param [type] $find */ function findFirstGreaterEqual(array $numbers, $find) { $length = count($numbers); $low = 0; $high = $length - 1; while ($low <= $high) { $mid = $low + (($high - $low) >> 1); if ($numbers[$mid] >= $find) { if ($mid == 0 || $numbers[$mid - 1] < $find) { return $mid; } else { $high = $mid - 1; } } else { $low = $mid + 1; } } return -1; } /** * 找到最后一个小于等于find的元素 * @param array $numbers * @param [type] $find */ function findLastLessEqual(array $numbers, $find) { $length = count($numbers); $low = 0; $high = $length - 1; while ($low <= $high) { $mid = $low + (($high - $low) >> 1); if ($numbers[$mid] <= $find) { if ($mid == $length - 1 || $numbers[$mid + 1] > $find) { return $mid; } $low = $mid + 1; } else { $high = $mid - 1; } } return -1; } /** * 循环数组中找指定元素 * @param array $numbers * @param [type] $find * * @return void * @date 2018/11/27 * @author yuanliandu <yuanliandu@qq.com> */ function searchCircularArray(array $numbers, $find) { $length = count($numbers); $low = 0; $high = $length - 1; while ($low <= $high) { $mid = $low + (($high - $low) >> 1); if ($numbers[$mid] === $find) { return $mid; } if ($numbers[$low] > $numbers[$mid]) { // 后半部分是有序数组 if (($numbers[$mid] < $find) && ($numbers[$high] >= $find)) { if ($numbers[$high] === $find) return $high; //在后半个区间内 $low = $mid + 1; } else { $high = $mid - 1; } } else { // 前半部分是有序的 if (($numbers[$low] <= $find) && ($numbers[$mid] > $find)) { // 在有序区间内 if ($numbers[$low] === $find) return $low; $high = $mid - 1; } else { $low = $mid + 1; } } } return -1; } /*** * 测试 */ $numbers = [1, 2, 3, 3, 3, 4, 5, 6, 8, 11, 13]; $find = 3; var_dump(findFirstEqual($numbers, $find));//找到第一个等于find的元素,结果:2 var_dump(findFirstGreaterEqual($numbers, $find));//找到第一个大于等于find的元素,结果:2 var_dump(findLastEqual($numbers, $find));//找到最后一个=find的元素,结果:4 var_dump(findLastLessEqual($numbers, $find));//找到最后一个小于等于find的元素,结果:4 //测试在循环数组中找到指定数字 $numbers = [9, 10, 1, 2, 3, 4, 5, 6, 7, 8]; $find = 2; var_dump(searchCircularArray($numbers, $find)); //结果:3