折半查找 python

折半查找，也称为二分查找，是一种在有序数组中查找特定元素的算法。它的基本思想是将数组分成两部分，通过比较中间元素和目标元素的大小关系，来确定目标元素在哪一部分中，然后再在该部分中继续查找，直到找到目标元素或者确定目标元素不存在为止。折半查找的时间复杂度为O(log n)，比顺序查找的时间复杂度O(n)更快。

在Python中，可以使用以下代码实现折半查找：

a = [-3, 4, 7, 9, 13, 45, 67, 89, 100, 180] # 有序数组
low = 0 # 数组上界
high = len(a) - 1 # 数组下界
m = 13 # 要查找的元素
k = -1 # 记录下标
while low <= high:
    mid = (low + high) // 2 # 取中间位置
    if m < a[mid]:
        high = mid - 1 # 在左半部分查找
    else:
        if m > a[mid]:
            low = mid + 1 # 在右半部分查找
        else:
            k = mid # 找到目标元素
            break
if k >= 0:
    print("m = %d, index = %d" %(m, k))
else:
    print("Not be found!")