二分查找Binary Search的思想:
以有序表表示静态查找表时,查找函数可以用二分查找来实现。
二分查找(Binary Search)的查找过程是:先确定待查记录所在的区间,然后逐步缩小区间直到找到或找不到该记录为止。
1二分查找的时间复杂度是O(log(n)),最坏情况下的时间复杂度是O(n)。
假设 low 指向区间下界,high 指向区间上界,mid 指向区间的中间位置,则 mid = (low + high) / 2;
具体过程:
1.先将关键字与 mid 指向的元素比较,如果相等则返回mid。
2.关键字小于 mid 指向的元素关键字,则在 [ low, mid-1 ]区间中继续进行二分查找。
3.关键字大于mid 指向的元素关键字,则在[ mid +1 , high] 区间中继续进行二分查找。
用Python实现二分查找示例:
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
29
30
31
32
33
34
35
36
37
38
39
40
|
>>> def find( self , num):
l = len ( self )
first = 0
end = l - 1
mid = 0
if l = = 0 :
self .insert( 0 ,num)
return False
while first < end:
mid = (first + end) / 2
if num > self [mid]:
first = mid + 1
elif num < self [mid]:
end = mid - 1
else :
break
if first = = end:
if self [first] > num:
self .insert(first, num)
return False
elif self [first] < num:
self .insert(first + 1 , num)
return False
else :
return True
elif first > end:
self .insert(first, num)
return False
else :
return True
>>> list_d = [ 'a' , 'b' , 'c' , 'd' , 'e' , 'f' , 'd' , 't' ]
>>> value_d = 't'
>>> aa = find(list_d,value_d)
>>> aa
True
>>> value_d = 'ha'
>>> aa = find(list_d,value_d)
>>> aa
False
|