【基础算法】【二分查找】二分查找及其各类变体（python）

今天梳理了一下二分查找及其各类变体，用python写的，代码及运行结果如下

函数体

查找target

# 查找target
# 找到 —— 返回索引，找不到 —— 返回-1
def Search(array, left, right, target):
    while left <= right:
        mid = left + int(0.5 * (right - left))
        if array[mid] < target:
            left = mid + 1
        elif array[mid] > target:
            right = mid - 1
        else:
            return mid
    return -1

查找第一个等于target的元素

# 查找第一个等于target的元素
# 找到 —— 返回索引，找不到 —— 返回-1
def SearchFirst(array, left, right, target):
    while left <= right:
        mid = left + int(0.5 * (right - left))
        if array[mid] < target:
            left = mid + 1
        elif array[mid] > target:
            right = mid - 1
        else:
            if mid == left or array[mid-1] != target:
                return mid
            else:
                right = mid - 1
    return -1

查找最后一个等于target的元素

# 查找最后一个等于target的元素
# 找到 —— 返回索引，找不到 —— 返回-1
def SearchLast(array, left, right, target):
    while left <= right:
        mid = left + int(0.5 * (right - left))
        if array[mid] < target:
            left = mid + 1
        elif array[mid] > target:
            right = mid - 1
        else:
            if mid == right or array[mid+1] != target:
                return mid
            else:
                left = mid + 1
    return -1

查找第一个大于等于target的元素

# 查找第一个大于等于target的元素
# 找到 —— 返回索引，找不到 —— 返回-1
def SearchFirstLarger(array, left, right, target):
    while left <= right:
        mid = left + int(0.5 * (right - left))
        if array[mid] < target:
            left = mid + 1
        else:
            if mid == left or array[mid-1] < target:
                return mid
            else:
                right = mid - 1
    return -1

查找最后一个小于等于target的元素

# 查找最后一个小于等于target的元素
# 找到 —— 返回索引，找不到 —— 返回-1
def SearchLastSmaller(array, left, right, target):
    while left <= right:
        mid = left + int(0.5 * (right - left))
        if array[mid] <= target:
            if mid == left or array[mid+1] > target:
                return mid
            else:
                left = mid + 1
        else:
            right = mid - 1
    return -1

函数调用及结果

array = [2,2,3,5,6,7,7,8,9,10,10]
print(Search(array, 0, len(array)-1, 6))
print(SearchFirst(array, 0, len(array)-1, 7))
print(SearchLast(array, 0, len(array)-1, 7))
print(SearchFirstLarger(array, 0, len(array)-1, 4))
print(SearchLastSmaller(array, 0, len(array)-1, 4))

4
5
6
3
2