《算法图解》笔记 i

二分查找

对于一个长度为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