algorithmic-二分法

Posted on | In | | Visitors:

二分查找

一般而言，对于包含了n个元素的列表，用二分查找最多需要log2n步，而简单查找最多需要n步。

对数

什么是对数？如何简单的说明这个概念？

对数是幂运算的逆运算

什么是大o表示法？

简单的python例子

下面是书上的栗子，但是用python3运行会报错：

  • 一个错是print函数不能打印，显示语法错误，应该修改成print(binary_search(my_list, 3)).
  • 另一个错是mid = (low + high)/2这里会报list indices must be integers, not float。解决方案是修改成mid = (low + high)//2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def binary_search(list, item):
	low = 0
	high = len(list)-1

	while low<=high:
		mid = (low+high)/2
		guess = list[mid]
		if guess == item:
			return mid
		if guess < item:
			low = mid+1
		else:
			high = mid-1
	return None

my_list = [1,3,5,7,9]

print binary_search(my_list, 3)
print binary_search(my_list, -1)

修改后可以运行的程序：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def binary_search(list, item):
	low = 0
	high = len(list)-1

	while low<=high:
		mid = (low+high)//2
		guess = list[mid]
		if guess == item:
			return mid
		if guess < item:
			low = mid+1
		else:
			high = mid-1
	return None

my_list = [1,3,5,7,9]

print(binary_search(my_list, 3))
print(binary_search(my_list, -1))

小练习

假设有一个包含128个名字的有序列表，你要使用二分查找在其中查找一个名字，请问最多需要几步才能找到?

7步
128=2*2*2*2*2*2*2

上面列表的长度翻倍后，最多需要几步?

8步