二分查找

排序系列文章链接：

O(n^2) (Jul 16, 2021)
O(nlogn) (Jul 16, 2021)
O(n) (Jul 16, 2021)
二分查找 (Jul 16, 2021)

二分查找针对的是一个有序的数据集合（有序数组），查找思想有点类似分治思想。
每次都通过跟区间的中间元素对比，将待查找的区间缩小为之前的一半，直到找到要查找的元素，或者区间被缩小为 0。

二叉查找的时间复杂度是: O(logn)

简单的二分查找

最简单的情况就是有序数组中不存在重复元素，查找值等于给定值的元素

二分查找的非递归实现

func BinarySearch(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    low := 0
    high := n - 1
    for low <= high {
        mid := low + ((high-low)>>1)
        if a[mid] == v {
            return mid
        } else if a[mid] > v {
            high = mid - 1
        } else {
            low = mid + 1
        }
    }

    return -1
}

二分查找的递归实现

func BinarySearchRecursive(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    return bs(a, v, 0, n-1)
}

func bs(a []int, v int, low, high int) int {
    if low > high {
        return -1
    }

    mid := low + ((high-low)>>1)
    if a[mid] == v {
        return mid
    } else if a[mid] > v {
        return bs(a, v, low, mid-1)
    } else {
        return bs(a, v, mid+1, high)
    }
}

编写二分查找代码，容易出错的 3 个地方

循环退出条件
- 注意是 low<=high，而不是 low
mid 的取值
- 实际上，mid=(low+high)/2 这种写法是有问题的。因为如果 low 和 high 比较大的话，两者之和就有可能会溢出。
- 改进的方法是将 mid 的计算方式写成 low+(high-low)/2。
- 更进一步，如果要将性能优化到极致的话，我们可以将这里的除以 2 操作转化成位运算 low+((high-low)»1)
low 和 high 的更新
- low=mid+1，high=mid-1。注意这里的 +1 和 -1，如果直接写成 low=mid 或者 high=mid，就可能会发生死循环。

二分查找应用场景的局限性

二分查找依赖的是顺序表结构，简单点说就是数组
二分查找针对的是有序数据
- 由于数组的插入、删除操作效率不高，二分查找只能用在插入、删除操作不频繁，一次排序多次查找的场景中
- 针对动态数据集合，一般使用二叉查找树。
数据量太小不适合二分查找
数据量太大也不适合二分查找
- 二分查找的底层需要依赖数组这种数据结构，而数组为了支持随机访问的特性，要求内存空间连续，对内存的要求比较苛刻。

二分查找的变形问题(应用更为广泛)

“十个二分查找九个错”，二分查找虽然原理极其简单，但是想要写出没有 Bug 的二分查找的变形问题并不容易。

假定数据是从小到大排列的，编写如下4种常见的二分查找的变形问题。

查找第一个值等于给定值的元素有序数据集合中存在重复的数据，我们希望找到第一个值等于给定值的数据

func BinarySearchFirst(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    low := 0
    high := n - 1
    for low <= high {
        mid := low + ((high - low) >> 1)
        if a[mid] > v {
            high = mid - 1
        } else if a[mid] < v {
            low = mid + 1
        } else {
            //确认一下这个 a[mid]是不是第一个值等于给定值的元素
            if mid == 0 || a[mid-1] != v {
                return mid
            } else {
                high = mid - 1
            }
        }
    }

    return -1
}

查找最后一个值等于给定值的元素

func BinarySearchLast(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    low := 0
    high := n - 1
    for low <= high {
        mid := low + ((high - low) >> 1)
        if a[mid] > v {
            high = mid - 1
        } else if a[mid] < v {
            low = mid + 1
        } else {
            //确认一下这个 a[mid]是不是最后一个值等于给定值的元素
            if mid == n-1 || a[mid+1] != v {
                return mid
            } else {
                low = mid + 1
            }
        }
    }

    return -1
}

查找第一个大于等于给定值的元素

func BinarySearchFirstGT(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    low := 0
    high := n - 1
    for low <= high {
        mid := low + ((high - low) >> 1)
        if a[mid] >= v {
            //确认一下这个 a[mid]是不是第一个值大于等于给定值的元素
            if mid == 0 || a[mid-1] < v { //如果 a[mid]前面已经没有元素，或者前面一个元素小于要查找的值 value，那 a[mid]就是我们要找的元素
                return mid
            } else {
                high = mid - 1
            }
        } else {
            low = mid + 1
        }
    }

    return -1
}

查找最后一个小于等于给定值的元素

func BinarySearchLastLT(a []int, v int) int {
    n := len(a)
    if n == 0 {
        return -1
    }

    low := 0
    high := n - 1
    for low <= high {
        mid := low + ((high - low) >> 1)
        if a[mid] > v {
            high = mid - 1
        } else {
            //确认一下这个 a[mid]是不是最后一个值小于等于给定值的元素
            if mid == n-1 || a[mid-1] > v {
                return mid
            } else {
                high = mid + 1
            }
        }
    }

    return -1
}