[TOC] ## 概述 查找框架 ``` int binarySearch(int[] nums, int target) { int left = 0, right = ...; while(...) { int mid = left + (right - left) / 2; if (nums[mid] == target) { ... } else if (nums[mid] < target) { left = ... } else if (nums[mid] > target) { right = ... } } return ...; } ``` 分析二分查找的一個技巧是：不要出現 else，而是把所有情況用 else if 寫清楚，這樣可以清楚地展現所有細節 計算 mid 時需要防止溢出，代碼中 left + (right - left) / 2 就和 (left + right) / 2 的結果相同，但是有效防止了 left 和 right 太大**直接相加**導致溢出 尋找一個數（基本的二分搜索） ``` int binarySearch(int[] nums, int target) { int left = 0; int right = nums.length - 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 if (nums[mid] > target) right = mid - 1; // 注意 } return -1; } ``` go 實現 <details> <summary>mian.go</summary> ``` package main import "fmt" func search(nums []int, target int) int { var left, right, mid int left = 0 right = len(nums) - 1 for left <= right { mid = left + (right-left)/2 if nums[mid] == target { return mid } else if nums[mid] > target { right = mid-1 } else if nums[mid] < target { left = mid+1 } } return -1 } func main() { fmt.Printf("%+v\n", search([]int{-1, 0, 3, 5, 6, 9, 12}, 2)) } ``` </details> <br/> 算法的缺陷 nums = \[1,2,2,2,3\]，target 為 2，此算法返回的索引是 2，沒錯。但是如果我想得到 target 的左側邊界，即索引 1，或者我想得到 target 的右側邊界，即索引 3，這樣的話此算法是無法處理的 **尋找左側邊界的二分搜索** ``` int left_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; // 搜索區間為 [left, right] while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { // 搜索區間變為 [mid+1, right] left = mid + 1; } else if (nums[mid] > target) { // 搜索區間變為 [left, mid-1] right = mid - 1; } else if (nums[mid] == target) { // 收縮右側邊界 right = mid - 1; } } // 檢查出界情況 if (left >= nums.length || nums[left] != target) return -1; return left; } ``` **尋找右側邊界的二分查找 ** ``` int right_bound(int[] nums, int target) { int left = 0, right = nums.length - 1; while (left <= right) { int mid = left + (right - left) / 2; if (nums[mid] < target) { left = mid + 1; } else if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] == target) { // 這里改成收縮左側邊界即可 left = mid + 1; } } // 這里改為檢查 right 越界的情況，見下圖 if (right < 0 || nums[right] != target) return -1; return right; } ```