# 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; } } ```