我們可以總結出二分查找的通用做法和常見變種。二分查找是一種在有序數組中高效查找元素的算法，時間復雜度為 O (log n)。

二分查找的通用模板

二分查找的核心思想是將搜索范圍不斷縮小一半，直到找到目標元素或確定其不存在。以下是通用模板：

cpp

int binarySearch(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;  // 未找到目標
}

常見變種及處理技巧

1.?查找插入位置（第一個大于等于目標的位置）

• 特點：返回第一個大于等于target的索引，若所有元素都小于target，則返回數組長度。
• 關鍵：循環結束時，left指向第一個大于等于target的位置。

cpp

int searchInsert(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) {left = mid + 1;} else {right = mid - 1;}}return left;  // 最終left即為插入位置
}

2.?二維矩陣查找

• 特點：將二維矩陣展開為一維有序數組。
• 關鍵：計算一維索引對應的二維坐標。

cpp

bool searchMatrix(vector<vector<int>>& matrix, int target) {int m = matrix.size(), n = matrix[0].size();int left = 0, right = m * n - 1;while (left <= right) {int mid = left + (right - left) / 2;int row = mid / n, col = mid % n;  // 轉換為二維坐標if (matrix[row][col] == target) {return true;} else if (matrix[row][col] < target) {left = mid + 1;} else {right = mid - 1;}}return false;
}

3.?查找元素的第一個和最后一個位置

• 特點：需要兩次二分查找，分別找到左邊界和右邊界。
• 關鍵：
  • 左邊界：第一個大于等于target的位置。
  • 右邊界：第一個大于target的位置減 1。

cpp

vector<int> searchRange(vector<int>& nums, int target) {auto lower = [&](int t) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] < t) {left = mid + 1;} else {right = mid - 1;}}return left;};int first = lower(target);if (first >= nums.size() || nums[first] != target) {return {-1, -1};}int last = lower(target + 1) - 1;  // 右邊界return {first, last};
}

4.?旋轉排序數組中的查找

• 特點：數組被旋轉后，左右半部分仍有序，但整體無序。
• 關鍵：通過比較nums[mid]與nums[0]的關系，確定哪半部分有序，再根據有序部分縮小范圍。

cpp

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;}if (nums[0] <= nums[mid]) {  // 左半部分有序if (target >= nums[0] && target < nums[mid]) {right = mid - 1;  // 目標在左半部分} else {left = mid + 1;  // 目標在右半部分}} else {  // 右半部分有序if (target > nums[mid] && target <= nums.back()) {left = mid + 1;  // 目標在右半部分} else {right = mid - 1;  // 目標在左半部分}}}return -1;
}

5.?尋找旋轉排序數組中的最小值

• 特點：最小值是旋轉點，左側元素都大于右側元素。
• 關鍵：比較nums[mid]與最右側元素的大小，確定旋轉點位置。

cpp

int findMin(vector<int>& nums) {int left = 0, right = nums.size() - 1;while (left <= right) {int mid = left + (right - left) / 2;if (nums[mid] <= nums[right]) {  // 最小值在左側right = mid - 1;} else {  // 最小值在右側left = mid + 1;}}return nums[left];  // 最終left指向最小值
}

二分查找的關鍵點總結

1. 循環條件：通常為left <= right，確保不漏掉最后一個元素。
2. 中間索引計算：使用mid = left + (right - left) / 2防止整數溢出。
3. 邊界調整：
   • 若目標在右側，left = mid + 1。
   • 若目標在左側，right = mid - 1。
4. 變種處理：
   • 查找左邊界：找到第一個大于等于target的位置。
   • 查找右邊界：找到第一個大于target的位置減 1。
   • 旋轉數組：通過比較nums[mid]與邊界元素，確定有序部分。

掌握這些技巧后，可以靈活應對各種二分查找的變種問題。