二分查找
对于一个长度为N的数组，简单查找最多需要N步；二分查找最多只需要logN步（约定底数为2）。
二分查找相较于简单查找，极大地提高了效率，但是二分查找的前提是列表是有序的，这也导致了诸多限制。
下面使用二分法编写一个查找算法。
Python实现
def binary_search(list,target):
#查找的起点和终点
low=0
high=len(list)-1
#
while (low<=high):
#若low+high为奇数，则向下取整
mid=(low+high)//2
temp=list[mid]
if target==temp:
return mid
elif temp>target:
high=mid-1
else:
low=mid+1
return None
if __name__ == '__main__':
test_list=[1,2,4,5,12,32,43]
print(binary_search(test_list,4))
print(binary_search(test_list, 44))
数组与链表
数组与链表的速度对比
| 数组 | 链表 | |
|---|---|---|
| 读取 | O(1) | O(N) |
| 插入 | O(N) | O(1) |
| 删除 | O(N) | O(1) |
选择排序
假如现在有一份购物清单，里面有多种商品，如何将这些商品按照价格顺序排列，下面使用选择排序方式，这种算法需要的时间为O(n^2)
Python实现
def select_sort(list):
sort_list=[]
max_num=0
for i in range(0,len(list)):
max_num=list[0]
for item2 in list:
if item2 > max_num:
max_num = item2
sort_list.append(max_num)
list.remove(max_num)
return sort_list
if __name__ == '__main__':
test_list=[231,32,533,234,22]
print(select_sort(test_list))
递归
想象这么一个问题，在一个大盒子里，有若干个小盒子，在这些小盒子里也可能有更小的盒子。在所有盒子中，其中一个盒子内有一把钥匙，如何找到这把钥匙?
有两种思路：
-
第一种：
image.png
-
第二种
image.png
哪一种思路更加清晰呢？我们用代码来实现一下：
- 第一种
首先新建两个类型盒子和钥匙：
class Box:
name=None
box=None
key=None
def __init__(self,name):
self.name=name
def set_box(self,box):
self.box=box
def set_key(self,key):
self.key=key
class Key:
name=None
def __init__(self,name):
self.name=name
查找算法：
def look_for_key(box):
pile_box=box
i=0
while pile_box is not None:
#默认取出盒子堆中的第一个
handle_box=pile_box[0]
print("取出了："+handle_box.name)
if handle_box.key is not None:
print("在"+handle_box.name+"中找到了钥匙")
return handle_box.key.name
elif handle_box.box is not None:
pile_box.append(handle_box.box)
print("将"+handle_box.box.name+"放入盒子堆")
pile_box.remove(handle_box)
return "没有找到钥匙"
测试数据：
if __name__ == '__main__':
#现在我创建一把钥匙
key1=Key("我是钥匙")
#现在我将钥匙放在盒子1中
b1 = Box("1号盒子")
b1.set_key(key1)
# 创建多个盒子，互相放置
b2=Box("2号盒子")
b2.set_box(b1)
b3=Box("3号盒子")
b3.set_box(b2)
b4=Box("4号盒子")
b4.set_box(b3)
b5=Box("5号盒子")
#将这些盒子放入一个大盒子
main_box=[b4,b5]
print(look_for_key(main_box))
输出：
取出了：4号盒子
将3号盒子放入盒子堆
取出了：5号盒子
取出了：3号盒子
将2号盒子放入盒子堆
取出了：2号盒子
将1号盒子放入盒子堆
取出了：1号盒子
在1号盒子中找到了钥匙
我是钥匙
- 第二种（递归方式）
新建类型还是使用之前的，主要是重新写一种查找算法：
def look_for_key(box):
print("打开了"+box.name)
if box.key is not None:
print("在" + box.name + "中找到了钥匙")
return
else:
look_for_key(box.box)
if __name__ == '__main__':
#现在我创建一把钥匙
key1=Key("我是钥匙")
#现在我将钥匙放在盒子1中
b1 = Box("1号盒子")
b1.set_key(key1)
# 创建多个盒子，互相放置
b2=Box("2号盒子")
b2.set_box(b1)
b3=Box("3号盒子")
b3.set_box(b2)
b4=Box("4号盒子")
b4.set_box(b3)
#将这些盒子放入一个大盒子
main_box=Box("主盒子")
main_box.set_box(b4)
look_for_key(main_box)
输出：
打开了主盒子
打开了4号盒子
打开了3号盒子
打开了2号盒子
打开了1号盒子
在1号盒子中找到了钥匙
总结以上两种查找方式：使用循环可能使效率更高，使用递归使得代码更易读懂，如何选择看哪一点对你更重要。
使用递归要注意基线条件和递归条件，否则很容易不小心陷入死循环。
image
网友评论