二分查找
題目描述
給定一個 n 個元素有序的（升序）整型數組 nums 和一個目標值 target ，寫一個函數搜索 nums 中的 target，如果目標值存在返回下標，否則返回 -1。
示例 1:
輸入: nums = [-1,0,3,5,9,12], target = 9
輸出: 4
解釋: 9 出現在 nums 中并且下標為 4
示例 2:
輸入: nums = [-1,0,3,5,9,12], target = 2
輸出: -1
解釋: 2 不存在 nums 中因此返回 -1
提示：
- 你可以假設
nums中的所有元素是不重復的。 n將在[1, 10000]之間。nums的每個元素都將在[-9999, 9999]之間。
核心算法
樸素二分查找算法
- x < t -> left = mid + 1 [left, right]
- x > t -> right = mid - 1 [left, right]
- x == t 返回結果
細節問題
-
循環結束的條件
left > right -
為什么是正確的？
二分查找算法之所以是正確的，是因為它利用了有序數組的性質，并通過不斷縮小搜索范圍的方式來快速定位目標元素。它的基本思想是將待搜索的數組分為兩部分，然后通過比較目標值與中間元素的大小關系，確定目標值可能存在的區間，然后在該區間內繼續二分查找，直到找到目標值或確定目標值不存在。
在每一次迭代中，二分查找算法將搜索區間縮小一半，因此它具有高效的搜索速度。由于每次都是將搜索區間減半，所以它的時間復雜度是O(log n)，其中n是數組的長度。相比于線性搜索算法的時間復雜度O(n)，二分查找算法在大規模數據集上具有更快的速度。
-
為什么時間快？
首先，二分查找算法每次將搜索區間縮小一半。假設待搜索的數組長度為n，在每次迭代中，查找區間的長度都會減半，因此經過k次迭代后，查找區間的長度將變為n/2^k。當查找區間的長度縮小到1時，就可以確定目標值的位置。所以，通過不斷將搜索區間減半，二分查找算法能夠在較少的比較操作中找到目標值，從而具有較快的時間復雜度。
其次，二分查找算法是基于有序數組進行查找。由于有序數組具有元素按照大小順序排列的特點，可以利用這個特點進行二分查找。每次比較目標值與中間元素的大小關系，可以確定目標值在左半部分或右半部分，從而縮小搜索范圍。這種有序性質使得二分查找算法能夠更快地定位目標值，避免了無效的搜索。
class Solution {
public:int search(vector<int>& nums, int target) {// 初始化左、右雙指針int left = 0, right = nums.size() - 1;while(left <= right){int mid = left + (right - left) / 2;if(nums[mid] == target) return mid;else if(nums[mid] < target) left = mid + 1;else right = mid - 1;}return -1;}
};
樸素二分模板
while(left <= right){// 防止漏出int mid = left + (right - left) / 2;if(....) right = mid - 1;else if(....) left = mid + 1;else return ......;}
