二分法查找
二分查找又称折半查找，优点是比较次数少，查找速度快，平均性能好。缺点是要求待查表为有序表。因此，折半查找方法适用于不经常变动而查找频繁的有序列表。
二分查找的工作原理
- 首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功。
- 否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。
- 重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。
二分查找的实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| def binary(l, val):
max = len(l)
min = 0
while min <= max:
mid = (max + min) // 2
if l[mid] > val:
max = mid - 1
elif l[mid] < val:
min = mid + 1
elif l[mid] == val:
print(mid)
break
else:
print('no')
def binary_rec(l, val, min, max):
mid = (max + min) // 2
if min > max:
print('no')
return 'no'
if l[mid] == val:
print(mid)
return mid
elif l[mid] < val:
return binary_rec(l, val, mid+1, max)
elif l[mid] > val:
return binary_rec(l, val, min, mid-1)
|