二分查找（下）

4种常见的二分查找变形问题

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

查找第一个值等于给定值

这里都默认数据是从小到达有序排序。

def search_first_equal(array, value):
    low = 0
    high = len(array) - 1
    while low <= high:
        mid = low + ((high-low)>>1)
        if array[mid] == value:
            if mid == 0 or array[mid-1] != value:
                return mid
            else:
                high = mid - 1
        elif array[mid] < value:
            low = mid + 1
        else:
            high = mid - 1

    return -1

思路是在找到mid的值等于value时，我们要知道mid之前是否有相同值的数据，那怎么判断呢：如果mid==0，那么说明在它前面没有元素了， 返回mid；如果mid前一个元素不等于value，那么该mid就是对应第一个值的元素位置。

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

def search_last_equal(array, value):
    low = 0
    high = len(array) - 1
    while low <= high:
        mid = low + ((high-low)>>1)
        if array[mid] == value:
            if mid == len(array)-1 or array[mid+1] != value:
                return mid
            else:
                low = mid + 1
        elif array[mid] < value:
            low = mid + 1
        else:
            high = mid - 1

    return -1

这个就很简单了，理解了前面的思路就行。

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

def search_first_greater_or_equal(array, value):
    low = 0
    high = len(array) - 1
    while low <= high:
        mid = low + ((high-low)>>1)
        if array[mid] >= value:
            if mid == 0 or array[mid-1] < value:
                return mid
            else:
                high = mid - 1
        else:
            low = mid + 1

    return -1

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

def search_last_less_or_equal(array, value):
    low = 0
    high = len(array) - 1
    while low <= high:
        mid = low + ((high-low)>>1)
        if array[mid] <= value:
            if mid == len(array) - 1 or array[mid+1] > value:
                return mid
            else:
                low = mid + 1
        else:
            high = mid - 1

    return -1

来自 https://leejnull.github.io/2020/03/04/2020-03-04-01/