4種常見(jiàn)的二分查找變形問(wèn)題

1. 查找第一個(gè)值等于給定值的元素
2. 查找最后一個(gè)值等于給定值的元素
3. 查找第一個(gè)大于等于給定值的元素
4. 查找最后一個(gè)小于等于給定值的元素

查找第一個(gè)值等于給定值

這里都默認(rèn)數(shù)據(jù)是從小到達(dá)有序排序。

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時(shí)，我們要知道m(xù)id之前是否有相同值的數(shù)據(jù)，那怎么判斷呢：如果mid==0，那么說(shuō)明在它前面沒(méi)有元素了， 返回mid；如果mid前一個(gè)元素不等于value，那么該mid就是對(duì)應(yīng)第一個(gè)值的元素位置。

查找最后一個(gè)值等于給定值的元素

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

這個(gè)就很簡(jiǎn)單了，理解了前面的思路就行。

查找第一個(gè)大于等于給定值的元素

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

查找最后一個(gè)小于等于給定值的元素

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

來(lái)自 https://leejnull.github.io/2020/03/04/2020-03-04-01/