二分查找

二分法对区间的定义就是不变量，要在二分查找的过程中，保持不变量，就是在while寻找中每一次边界的处理都要坚持根据区间的定义来操作，这就是循环不变量规则。

• 左闭右闭即[left, right]
• 左闭右开即[left, right)

1. 基本二分查找(左闭右闭即[left, right])

因为定义target在[left, right]区间，所以有如下两点：

• while (left <= right) 要使用 <= ，因为left == right是有意义的，所以使用 <=
• if (nums[middle] > target) right 要赋值为middle - 1，因为当前这个nums[middle]一定不是target，那么接下来要查找的左区间结束下标位置就是 middle - 1。

func search(nums []int, target int) int {
    left, right := 0, len(nums)-1
    // 初始化 right 的赋值是 len(nums)-1，即最后一个元素的索引，而不是len(nums)。
    for left <= right{
        
        mid := left + (right - left) / 2
        if nums[mid] > target{
            right = mid - 1
        }else if nums[mid] < target {
            left = mid + 1
        }else{
            return mid
        }
    }
    return -1
}

2. 基本二分查找(左闭右开即[left, right)

因为定义target在[left, right)区间，所以有如下两点：

• while (left < right)，这里使用 < ,因为left == right在区间[left, right)是没有意义的
• if (nums[middle] > target) right 更新为 middle，因为当前nums[middle]不等于target，去左区间继续寻找，而寻找区间是左闭右开区间，所以right更新为middle，即：下一个查询区间不会去比较nums[middle]

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

有序数组 nums = [1,2,2,2,3]，target = 2，此算法返回的索引是 2，基本二分查找无法满足以下场景：

• target 的左侧边界，即索引 1
• target 的右侧边界，即索引 3

3. 寻找左侧边界的二分搜索

func search(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right{
        mid := left + (right - left) / 2
        if nums[mid] > target{ // [left, mid)
            right = mid
        }else if nums[mid] < target {
            left = mid + 1
        }else if nums[mid] ==  target{  // 找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid) 中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。
             right = mid
        }
    }
    return left
}

4. 寻找右侧边界的二分搜索

func search(nums []int, target int) int {
    left, right := 0, len(nums)
    for left < right{
        mid := left + (right - left) / 2
        if nums[mid] > target{ // [left, mid)
            right = mid
        }else if nums[mid] < target {
            left = mid + 1
        }else if nums[mid] ==  target{ // 当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的下界 left，使得区间不断向右收缩，达到锁定右侧边界的目的。
             left = mid + 1
        }
    }
    return left - 1
}

ref:
https://www.cnblogs.com/kyoner/p/11080078.html
https://leetcode-cn.com/problems/binary-search/solution/dai-ma-sui-xiang-lu-dai-ni-xue-tou-er-fe-5a77/