# 1、二分查找介绍 二分查找(Binary search)也称折半查找，是一种效率较高的查找方法。但是，二分查找要求线性表中的记录必须按关键码有序，并且必须采用顺序存储 # 2、二分查找原理 二分查找算法的原理如下： ``` 1. 设置查找区间：low = 0；high= n； 2. 若查找区间[low, high]不存在，则查找失败；否则转步骤3 3. 取中间位mid = (low + high) / 2；比较 target 与 arr[mid]，有以下三种情况： 3.1 若 target < arr[mid]，则high = mid - 1；查找在左半区间进行，转步骤2； 3.2 若 target > arr[mid]，则low = mid + 1；查找在右半区间进行，转步骤2； 3.3 若 target = arr[mid]，则查找成功，返回 mid 值 ``` # 3、二分查找代码实现 1.二分查找：给定一个 n个元素有序的（升序）整型数组 nums和一个目标值 target，写一个函数搜索 nums中的target，如果目标值存在返回下标，否则返回-1。 ``` class Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer */ function search($nums, $target) { $start = 0; $end = count($nums); $mid = floor(($start + $end) / 2); for ($i = $start; $i < $end; $i++) { if ($nums[$i] > $target) { $end = $mid --; } elseif ($nums[$i] < $target) { $start = $mid ++; } else { return $i; } } return -1; } } ``` 2.搜索插入位置：给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。 请必须使用时间复杂度为`O(log n)`的算法。 ``` class Solution { /** * @param Integer[] $nums * @param Integer $target * @return Integer */ function searchInsert($nums, $target) { $n = count($nums); if ($n === 0) return 0; if ($target < $nums[0]) return 0; if ($target > end($nums)) return $n; $l = 0; $r = $n - 1; while ($l < $r) { $mid = $l + floor(($r - $l) / 2); if ($nums[$mid] === $target) return $mid; // 当中间元素严格小于目标元素时，肯定不是解 if ($nums[$mid] < $target) { // 下一轮搜索区间是 [mid+1, right] $l = $mid + 1; } else { $r = $mid; } } return $l; } } ```