python二分查找

python二分查找

# 查找数据

import random

# nums = [random.randint(1,101) for x in range(10)]
nums = [27, 19, 74, 67, 25, 89, 34, 3, 93, 95]
print(nums)

print(nums.index(3))


# print(nums.index(5))
# 问题1 当查找 不存在的数据会报错

# 解决问题:
def find_element(nums, ele):
    for item in enumerate(nums):
        if ele == item[1]:
            return item[0]
    else:
        return -1


# 测试
print(find_element(nums, 35))
print(find_element(nums, 5))


# 问题2 查找效率太低
# 如果将数据放大100倍,在1000个数据中查找数据,那么平均每个数据的查找比较次数是 500次
# 二分查找法

def binary_search(nums, ele):
    # 如果不在列表中不需要查找
    if ele not in nums:
        return -1
    # 左边界
    start = 0
    # 右边界
    stop = len(nums) - 1
    # 左边大于右边才可以查找
    while start <= stop:
        # 确定中值
        mid = (start + stop) // 2
        # 判断,改变左
        if ele > nums[mid]:
            start = mid + 1
        # 判断改变右
        elif ele < nums[mid]:
            stop = mid - 1
        # 找到
        else:
            return mid


# 二分查找必须基于有须数据,所以对数据进行排序
nums.sort()

print(binary_search(nums, 3))
print(binary_search(nums, 95))
print(binary_search(nums, 5))