[AlgoGo]二分查找

二分查找算法用在有序的数据集合中查找目标数据，时间复杂度为O(logn)，但限制条件较多。

二分查找的限制

1. 二分查找依赖随机存取，所以只能用数组实现，内存要求高。
2. 二分查找针对有序数据，需要提前对数据进行排序。
3. 数据集太小不适合，可能直接遍历比二分效率更高。
4. 数据集太大不适合，依赖数组连续内存，对大块内存需求要求高。

实现二分查找的关键点

1. 循环退出条件： start >= end
2. mid的取值，避免越界，使用 mid = start + ((end - start)>>1)
3. 更新范围 mid小于目标值：start = mid + 1 mid大于目标值：end = mid - 1

二分查找的变体问题

1. 查找第一个值等于给定值的元素
2. 查找最后一个值等于给定值的元素
3. 查找第一个值大于等于给定值的元素
4. 查找最后一个值小于等于给定值的元素

变种问题需要考虑的其实是当遇到a[mid] == target 的情况时该如何维护上下界。如果要找第一个值等于给定值的元素，则应将a[mid] == target条件合并到a[mid]>target中，将上界更新为mid - 1，这样才能向下逼出第一个元素。而找最后一个的时候则是将相等条件合并到小于中，向上逼出最后一个。