二分搜索

[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 实现

mian.go

``` 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)) } ```

算法的缺陷 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; } ```