数据结构与算法——二分查找

        二分查找算法常用于在具有单调性的数组中，以logn的时间复杂度快速查找某个目标值是否存在于该数组中，如果存在还能够返回目标值在数组中的索引下标，常见的二分查找算法有开区间写法、半开区间写法以及闭区间写法，这三种写法的区别是左右指针所指的值是否在二分查找的范围之内，开区间的二分查找的范围是(l，r)，半开区间的二分查找的是(l，r]或者[l，r)，而闭区间的二分查找的是[l，r]，三种写法掌握一种即可，这里提供一个Python实现的闭区间二分查找算法模版：

lst = [1, 3, 5, 5, 5, 6, 8, 9]
target = 5l, r = 0, len(lst) - 1
while l <= r:mid = (l + r) // 2if lst[mid] < target:l = mid + 1else:r = mid - 1
ans = l 
print(ans) # 2

        上述算法的ans是从左到右第一个大于等于target的数的位置，也就是说有以下三种情况：

        1. 如果target在lst中且无重复的target存在，ans即为target的位置。

        2. 如果target在lst中且有重复的target存在，ans为第一个target出现的位置。

        3. 如果target不在lst中，ans为从左到右第一个大于target的数的位置，此时如果target大于lst中的所有数，ans为lst的长度（即len(lst)），而如果target小于lst中的所有数，ans即为0。

        如果要查找从右到左第一个小于等于target的数的位置，则可以使用以下的闭区间二分查找算法模版：

lst = [1, 3, 5, 5, 5, 6, 8, 9]
target = 5l, r = 0, len(lst) - 1
while l <= r:mid = (l + r) // 2if lst[mid] <= target:l = mid + 1else:r = mid - 1
ans = r 
print(ans) # 4

        上述算法也有如下三种情况：

        1. 如果target在lst中且无重复的target存在，ans即为target的位置，此时与第一个算法模版结果相同。

        2. 如果target在lst中且有重复的target存在，ans为最后一个target出现的位置。

        3. 如果target不在lst中，ans为从右到左第一个小于target的数的位置，此时如果target大于lst中的所有数，ans为lst的长度减一（即len(lst) - 1），而如果target小于lst中的所有数，ans即为-1。