二分法查找

适用条件：数据量较大，已经排好顺序，所找数据存在

在有序的N个元素的数组中查找用户输进去的数据x。

算法如下：

1.确定查找范围front=0，end=N-1，计算中项mid=（front+end）/2。

2.若a[mid]=x或front>=end,则结束查找；否则，向下继续。

3.若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内，则把mid+1的值赋给front，并重新计算mid，转去执行步骤2；若a[mid]>x，说明待查找的元素值只可能在比中项元素小的范围内，则把mid-1的值赋给end，并重新计算mid，转去执行步骤2。

 

# 二分法查找
def BinarySearch(arr, key):
      # 记录数组的最高位和最低位
    min = 0
    max = len(arr) - 1
    if key in arr:
        # 建立一个死循环，直到找到key
         while True:
            # 得到中位数
             # 这里一定要加int，防止列表是偶数的时候出现浮点数据
             middle = int((min + max) / 2)
             # key在数组左边
             if arr[middle] > key:
                max = middle - 1
             # key在数组右边
             elif arr[middle] < key:
                min = middle + 1
             # key在数组中间
             elif arr[middle] == key:
                print(str(key) + "在数组里面的第" + str(middle) + "个位置")
                return arr[middle]
    else:
     print("没有该数字!")
data1 = [1,3,5,7,9]
BinarySearch(data1,6)