算法之二分法查找

# 二分法查找模板
def bin_search(nums, val):
    if len(nums) == 0:
        return -1
    left = 0
    right = len(nums) - 1
    # 当left 和right相邻 或者left等于right的时候停止循环
    while left + 1 < right:
        mid = (left + right) // 2
        if nums[mid] == val:
            # 当有多个相同的元素时， 返回第一个出现的位置, 如果想返回最后一位出现的位置，则使用 left = mid
            right = mid
        elif val < nums[mid]:
            right = mid - 1
        else:
            left = mid + 1
    # 因为有可能出现left和right相邻 或者left等于right的时候停止循环，兜底判断
    if nums[left] == val:
        return left
    if nums[right] == val:
        return right
    return -1


if __name__ == ‘__main__‘:
    nums = [1, 2, 2, 2, 3, 4, 4, 5, 5]
    print(bin_search(nums, 6))