二分查找只有一个思想，那就是：逐步缩小搜索区间

力扣

二分查找重点

• 写成 for left < right 退出循环的时候有 left == right 成立，双指针重合
• 区间 [left..right] 划分只有以下两种情况：
  • 分成 [left..mid] 和 [mid + 1..right]，分别对应 right = mid 和 left = mid + 1
  • 分成 [left..mid - 1] 和 [mid..right]，分别对应 right = mid - 1 和 left = mid，这种情况下。需要将 int mid = (left + right) / 2 改成 int mid = (left + right + 1) / 2，否则会出现死循环，这一点不用记，出现死循环的时候，把 left 和 right 的值打印出来看一下就很清楚了
• 退出循环 left == right，如果可以确定区间 [left..right] 一定有解，直接返回 left 就可以，否则还需要对 left 这个位置单独做一次判断

分析二分查找的技巧是：不要出现 else，而是把所有情况用 else if 写清楚，清楚地展现所有细节

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 ...; 
}

寻找一个数

func binarySearch(nums []int, target int) 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 {
			left = mid + 1 // 下个搜索区间 [mid+1, right]
		} else if nums[mid] > target {
			right = mid - 1 // 下个搜索区间 [left, mid-1]
		}
	}
	return -1
}

排序数组中的搜索问题

统计 target 数字出现次数，即用二分法查找左右边界

1. 初始化 左边界 i = 0 右边界 j = len(nums) - 1
2. 循环二分：当闭区间 [i, j] 无元素时跳出
   1. 计算中点 mid
   2. 若 nums[mid] < target 则 target 在 [mid+1, j] 执行 i = m + 1
   3. 若 nums[mid] > target 则 target 在 [i, mid-1] 执行 j = m - 1
   4. 若 nums[mid] == target 则 右边界 在 [mid+1, j] 左边界在 [i, mid-1] 分两种情况
      1. 若查找 右边界 right 则执行 i = mid + 1 跳出时 i 指向右边界
      2. 若查找 左边界 left 则执行 j = mid - 1 跳出时 j 指向左边界

func binarySearch(nums []int, target int, lower bool) int {
	left, right, ans := 0, len(nums)-1, len(nums)
	for left <= right {
		mid := (left+right) / 2
		if nums[mid] > target || // 找第一个大于 target 右边界
			(lower && nums[mid] >= target) { // 找第一个等于 target 左边界
			right = mid-1
			ans = mid
		} else {
			left = mid+1
		}
	}
	return ans
}

func search(nums []int, target int) (ans int) {
	leftIdx := binarySearch(nums, target, true)
	rightIdx := binarySearch(nums, target, false) - 1
	if leftIdx <= rightIdx && 
		rightIdx < len(nums) && 
		nums[leftIdx] == target &&
		nums[rightIdx] == target {
		ans = rightIdx - leftIdx + 1
	}
	return
}