使用二分法实现在一个有序列表中查找指定的元素_给定一组有序序列,用随机化二分查找的方法查找某元素x。提示:随机化二分查找方法

二分法是一种快速查找的方法，时间复杂度低，逻辑简单易懂，总的来说就是不断的除以2除以2…

例如需要查找有序数组arr里面的某个关键字key的位置，那么首先确认arr的中位数或者中点center，下面分为三种情况：

1假如arr[center]>key，说明key在arr中心左边范围；
2假如arr[center]<key，说明key在arr中心右边范围；
3假如arr[center]=key，说明key在arr中心。
范围每次缩小一半，写个while的死循环知道找到为止。
二分法查找非常快且非常常用，但是唯一要求是要求数组是有序的

方法1:二分法的代码如下,先判断key是否在arr里然后再查询

 def BinarySearch(arr, key):
     # 记录数组的最高位和最低位
     min = 0
     max = len(arr) - 1
 
     if key in arr:
         # 建立一个死循环，直到找到key
         while True:
             # 得到中位数
             # 这里一定要加int，防止列表是偶数的时候出现浮点数据
             center = int((min + max) / 2)
             # key在数组左边
             if arr[center] > key:
                 max = center - 1
             # key在数组右边
             elif arr[center] < key:
                 min = center + 1
             # key在数组中间
         
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18