二分查找

二分查找的基本情况不过多介绍，非常基础。

有难度的是找到适它适用的场景，用它或者它的变种来解决复杂问题。几个值得关注的点，也是容易犯错的点

最基本的原则是，二分查找只能针对有序的数组
边界条件，每个情况到底是用<还是≤（或>还是≥）
当出现重复的值，到底是取左边第一个为结果，还是取右边最后一个为结果，也就是左边界问题，和右边界问题

最基础的二分查找模板

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
        } else if nums[mid] > target { // 目标值在左半部分，注意
            right = mid - 1
        }
    }
    return -1 // 未找到
}

值得关注的循环条件中为什么是≤ 而不是<？

因为数组最后一个元素的索引是len(nums)-1, 而不是len(nums)，索引为len(nums)是越界的。

可以理解为：

当right值为len(nums)-1时，相当于左右都是闭区间，可以取到，[left,right]，故循环条件是left≤right，可以取到right 的值
当right值为len(nums)时，相当于是左开右闭区间，只能取到左边，取不到右边，[left,right)，故循环条件是left<right, 此时right的索引值实际为数组最后一个元素的索引值+1。

这个非常简单，但是就是因为太简单而非常容易忽略导致犯错，我遇到过在面试中白板写代码卡在这个地方几次，高压环境下又没有定位到问题。

第二个值得关注的点就是不同情况下，有时用 left = mid + 1, right = mid -1,有时却是用right = mid 或者left = mid。

其实很简单，因为mid已经搜索过了，所以我们要在新区间里剔除掉mid的索引，让新区间取不到mid，接着去搜索[left,mid-1]左右闭区间，[mid+1,right]左右闭区间，就这么简单。

左右边界问题

比如有序数组[1,2,2,2,3]，target为2，在第一个判断中nums[mid] ==target就返回了索引2，也就是三个2元素里中间的元素。那如果要求返回第一个2，最左边界的元素呢，或者最右边界的元素呢？

这也就是二分查找的一个缺陷，所以大部分场景是无重复元素的数组，或者特殊情况用特殊的办法来缩小区间，最后让问题变成在一个无重复元素的小区间里查找的问题。

最左边界

func leftBound (nums []int, target int) int {
  left:=0
  right := len(nums)
  for left < right{
    mid := left + (right- left) /2
    if nums[mid] == target{
      right = mid
    }else if nums[mid] > target{
      right = mid
    }else if nums[mid] < target {
      left = mid +1
    }
  }
  if left < 0  || left >= len(nums) {
    return -1
  }
  if nums[left] == target{
    return left
  }
  return -1
}

为什么nums[mid] >target情况下 right = mid ，因为我们用的right为len(nums) ，所以条件为left<right，所以是左闭右开区间，right = mid之后，在新子区间 nums[mid]就已经取不到了。

如果right为len(nums)-1，当然这种情况下right就该等于mid-1，因为左右都是闭区间了。

可以再写一版

func left_bound(nums []int, target int) int {
    left := 0
    right := len(nums) - 1
    // 搜索区间为 [left, right]
    for left <= right {
        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
        }
    }
    // 判断 target 是否存在于 nums 中
    // 如果越界，target 肯定不存在，返回 -1
    if left < 0 || left >= len(nums) {
        return -1
    }
    // 判断一下 nums[left] 是不是 target
    if nums[left] == target {
        return left
    }
    return -1
}

为什么这样可以搜索左边界呢？

因为在nums[mid] == target时，我们不立即返回 mid，而是继续缩小搜索区间的上边界或者说左边界，在区间[left,mid)中继续搜索，就可以锁定左边界。

再来看右边界问题，同理只需要在nums[mid] == target时，不返回mid，继续增大左边界（向右压缩）。

func binarySearch(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        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 {
            // 直接返回
            return mid
        }
    }
    // 直接返回
    return -1
}
func leftBound(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        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 {
            // 别返回，锁定左侧边界
            right = mid - 1
        }
    }
    // 判断 target 是否存在于 nums 中
    if left < 0 || left >= len(nums) {
        return -1
    }
    // 判断一下 nums[left] 是不是 target
    if nums[left] == target {
        return left
    }
    return -1
}

func rightBound(nums []int, target int) int {
    left, right := 0, len(nums)-1
    for left <= right {
        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
        }
    }
    // 判断 target 是否存在于 nums 中
    // if left - 1 < 0 || left - 1 >= len(nums) {
    //     return -1
    // }

    if right < 0 || right >= len(nums) {
        return -1
    }
    if nums[right] == target {
        return right
    }
    return -1
}

二分查找中的细节

二分查找