Skip to content

Latest commit

 

History

History
391 lines (276 loc) · 18.1 KB

简明算法系列：顺序查找和二分法.md

File metadata and controls

391 lines (276 loc) · 18.1 KB
Raw

简明算法系列：顺序查找和二分法

查找(searching)是计算机算法的重要组成部分。它的内容本身理解起来不难，但真要动手写起来，可能会有这样那样的细节问题。而且感觉除非经常和算法打交道，否则过段时间就很容易忘记具体细节，所以这里尝试着通过例子把要点总结起来。既希望是一个实践性比较强的教程，也是自己的一个备忘录。

这篇笔记会用Python，原因有几个。一来当然是自己习惯Python，二来Python天生好懂，三来这里有个在线的Python解释器：http://repl.it/languages/Python/ 可以零安装零配置零折腾地开始写Python，方便到令人发指。而由于Python本身就有点像伪代码，所以习惯用C或者其它语言的朋友应该也不会感到隔阂。

Python由于太过方便，本身自带了很多查找和排序的功能，所以这个例程会适时地禁用某些东西（比如，总不能直接调用sort()来写一个快速排序吧）。这些会在各个例子里注明，也因此会使得一些代码看起来不那么Pythonic或者解法是sub-optimal。

按照我的其它笔记的模式，从几个例子开始讲起，从最简单的开始说。谨慎建议对于下面的例子，无论看起来多简单，或者用Python，或者用上你熟悉的语言，动手自己写一下，相信会有不一样的发现。

这一节是关于顺序查找和二分法。下一节则是哈希表。

1. 顺序查找

例1 给定一个整数s和一个整数数组a，判断s是否在a中。（注：不能用Python自带的if s in a）

既然没有注明a有什么特性，我们就只能假定它是一个很随机的数组。要判断s是否在a中，我们能做的，也就是逐个访问a中的元素并和s比较。一旦找到，返回True，a遍历完了还没找到，则返回False。这个过程实现起来非常简单：

def seq_search(s, a):
    for i in range(len(a)):
        if s == a[i]:
            return True
    return False

给几个测试例子

a = [13,42,3,4,7,5,6]
s = 7
print seq_search(s,a)

a2 = [10,25,3,4,780,5,6]
s = 70
print seq_search(s,a2)

如无意外的话，会输出：

True
False

如果要算它的时间复杂度也简单，各种情况下，复杂度是这样的：

情况 最好 最坏 平均
找到了 1 n n/2
没找到 n n n

用Big-O来表示，就是复杂度是O(n)。对于没找到的情况，数组总是要遍历一次的。而对于元素在数组中的情况，则要分运气好坏，或许第一个就中了，或许最后一个才是，平均而言，则是n/2。

例2 注册网站账号时，用户名常常要符合某些要求，比如不能含有英文的;!~这三个字符。写一个函数，读入用户输出的用户名，返回“用户名合法”或者“用户名不合法”。

一个直观的解法是这样：

def username_check():
    username = input('输入一个用户名')
    
    for s in ';!~':
        if seq_search(s,username):
           return '用户名不合法'
    return '用户名合法'

当然也可以这样：

def username_check2():
    username = input('输入一个用户名')
    
    for i in range(len(username)):
        if seq_search(username[i],';!~'):
            return '用户名不合法'
    return '用户名合法'

这里都是多次调用我们之前写好的seq_search(s,a)。

2. 二分查找和分治法

上述的顺序查找看起来简单，技术含量不高，但对于一般的数组，确实也只能这样查找了。但假如数组本身是排序好的，则在查找的时候会省事一些。想象一下，如果你要在一堆人中找出体重和你一样的人，一般情况下也没有特殊的办法，只能逐个去比，并期望于早一点找出那个人。但假如告诉你，面前的这一堆人已经按体重由轻到重排列好了，那显然我们不会再一个个去比，而是先瞄一眼，看看有哪个人可能体重和你无限接近，然后和他比较。如果你比他重，说明你要找的人在这个人的右边，如果你比他轻，则说明你要找的人在这个人的左边。于是我们就把范围缩小了，下一次的搜索，我们只需要其中一边去找。而对于这半边，我们又可以故伎重演，找一个人，然后再将这半边队列分成两半。

这其实就是二分查找。只不过对于数字，我们通常无法先主观地找出一个“看起来差不多的”，因此我们会习惯性地从队列中间将队列等分劈成两半。

来看一个具体的例子吧。

a = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10，11, 12]
s = 3

同样地，我们想知道3是否在数组里。因为我们知道数组已排序好，所以我们可以直接先看数组的中间值。在这里是6。由于3<6，我们于是知道了3只可能在数组的左半边。接下来我们只需要在子数组

a_sub = [0, 1, 2, 3, 4, 5]

里找就可以了。对于a_sub，我们也是取中间的那个值，在这里是2（5/2取整，a[2]=2）。于是我们取右半边：

a_sub_sub = [3,4,5]

再取中间值4。然后再取左半边：

a_sub_sub_sub = [3]

这时的中间值刚好就是3了。通过不断缩小范围，我们成功地定位到3这个值。

请原谅略不雅观的命名。

二分查找其实就是这样：数组不断裂变成原来的一半，（最坏情况下）最终到只剩一个元素。而运气好的时候，某一次的中间值刚好就等于你要找的那个值。

下面我们写出以上过程的代码。

例3 写一个函数实现二分查找来判断整数s是否在升序排列的整数数组a当中。

def binary_search(s,array):
    found = False
    
    # left 和 right定义子数组的边界，一开始搜索的是整个数组
    left = 0
    right = len(array)-1
        
    while left <= right:
        mid = (left+right) //2
        if array[mid] == s:
            return True
        if s < array[mid]:
            # 到左边去找
            right = mid-1
        else:
            # 到右边去找
            left = mid + 1
            
    return False

left和right两个变量，定义我们搜索的子数组的边界。一开始我们查找的是整个数组。以后逐次按照上面的步骤，搜索左半边或者右半边。 只要是左边边界比右边边界小或者相等，就说明数组还至少有一个元素，那我们就持续执行这个裂变的循环。如果找到了，就停止搜索，如果在while循环里一直找不到，那么最后就返回False。

如果你回顾上述过程，会发现每一次进入一个子数组，我们做的事情是一样的：取中间值，然后比较，取左边/右边。于是这个过程也可以用递归来实现。

如果对递归没有概念的话，可以先看看下面的例子。有接触过递归的朋友就可以果断跳过啦。

例4 写一个函数对1-100之间的整数求和。

非递归的解法

def cal_sum(num):
    sum = 0
    for i in range(1,num+1):
        sum += i
    return sum

上面的求和方法非常直观，从1到100做一个循环。而用递归的思想来解决是这样的：对1-100求和，其实等于是100加上前99个的和(sum99)，而前99个的和，又等于99+sum98，如此反复。把这个过程表示出来其实就是：

sum(i) = i + sum(i-1)

因此1-100求和的递归解法可以是：

def cal_sum(i):
    if i == 1:
        return 1
    return i + cal_sum(i-1)

是不是看起来更简洁？我们一开始想知道cal_sum(100)，通过递归，我们转而去求解cal_sum(99)，cal_sum(99)又会去调用cal_sum(98)。那么到哪里是个头呢？

一个递归函数，必须有一个终止的条件，不然的话就等于是一级一级爬向无底深渊。在上述这个函数里，我们的终止条件就是假如i==1，则不再继续递归，而是返回1。

明白了递归的基础知识，我们就可以将二分查找用递归来实现了。如下所示（慎重建议自己先写一遍）：

def binary_search_rec(s,array):
    
    if len(array) == 0:
        # 数组已被掏空
        return False
            
    mid = (len(array)-1) //2
    
    if array[mid] == s:
        # 找到啦
        return True
    elif s < array[mid]:
        # 要找的人在左边
        return binary_search_rec(s, array[:mid])
    else:
        # 要找的人在右边
        return binary_search_rec(s, array[mid+1:])

使用递归，要注意终止递归的条件是什么，在这里，如果数组已经是空了，则表示没找到，不再递归，返回False，如果找到，也是直接返回，不再折腾子数组了。要注意递归函数被调用时，前面要加return。这是因为这里的递归就好像一层一层进入一个深渊去寻找宝藏，而一旦找到，不能简单地满足于在深渊里喊一声“我找到了”，而是要逐层传递回来，直到地面上的人（第一级函数）也收到了信息。

二分查找显然要比顺序查找省时间，每一次分裂，搜索的长度都变为之前的二分之一。假设一个数组原来的长度为n，则一次之后，变为n/2，再裂变后变为n/4,n/8...不难看出其时间复杂度是O(log(n))。

例5 一个本来按升序排序好的数组被切成两部分，这两部分调换位置变成一个新数组。用二分查找找出数组中的最小元素。假设数组不含重复元素。

比如，一个数组本来是a=[1,2,3,4,5,6,7,8,9]。现在沿着4和5之间切一刀，调换位置，变成一个新数组a=[5,6,7,8,9,1,2,3,4]。

这是LeetCode的153题，难度标记为中等。

考虑一个没被拦腰截断的升序数组，除了最大的那一个，其余所有元素，当向右望的时候，都会发现右边的元素比它大。这是正常的情况。因此，假如当你向右望而发现有元素比你小的时候，可想而知你右边的那一块是被动过手脚的。也就是那个“切断点”就藏在右边。反过来想，如果右半边没有一个先降后升的过程，那你不可能找到比你小的元素。而先降后升的那个转折点，就是我们要找的。因此，你可以把搜索范围缩小到右半边。而如果右半边的元素比你大，而将搜索范围转到左半边。这其实和我们上面的例4很接近。

def slice_point(num,left,right):
    if left==right:
        # 只剩一个元素
        return num[right]
        
    mid = (right+left)//2
    
    if num[mid]>num[right]:
        return slice_point(num,mid+1,right)
    else:
        return slice_point(num,left,mid)

注意我们这里将left和right也作为参数传递，这样是为了更直观，其实也完全可以不用。就像上面的那个例子一样，直接对Python的list进行slice操作(e.g. num[mid:])。代码和例3非常像，但你发现几乎相同的一段代码，却可以用来回答不同的问题。

练习 试着用循环（而不是递归）来实现上述查找。

这个就不给答案了。

例6 用二分查找实现开平方根函数square(x,p)。x是被开方根的数，假定输入都为非负整数，p是误差上限，输出一个浮点数结果。

这是LeetCode的69题，略有改动。原题是输出一个整数，这里直接输出浮点数，难度其实是降低了。原题难度标记为中等。

如何用二分查找思考这个问题？

我们要查找的，其实是某数的近似平方根。那么供我们查找的数组在哪里呢？搜索范围是什么？

显然，一个整数的平方根，不会小于0，也不会大于他本身。于是我们的搜索范围，其实就可以定位[0, x]。在这个范围里我们应用二分搜索，取中间值mid=0.5x，如果mid*mid > x，说明我们改走左半边。反之，走右半边。代码如下：

def square(x,p):
    return square_helper(x,0.0,float(x),p)


def square_helper(x,left,right,p):

    if abs(left-right) < p*2:
        # 左边右边距离已经很小了
        #print (left+right)/2.0
        return (left+right)/2.0
    
    # 折半
    mid = float((left+right)/2.0) 
    
    
    if mid*mid - x > 0:
        return square_helper(x,left,mid,p)
    else:
        return square_helper(x,mid,right,p)

你可以通过随意控制p来输出不同精度的值。到这里你可以看到，无论是用循环还是递归，二分查找的套路都是极其类似的：

  • 一个终止条件，前面那些数组的例子，终止条件就是：找到或者没找到（一个确定的答案）。开平方根，条件就是，满足精度要求。注意，程序的编写还应考虑各种情况。在各种情况下都应有退出机制。
  • 取中间值，然后根据中间值的情况，确定往左还是往右。

就这么简单。至于是用循环还是递归，对于一个算法题来说，大部分时候是一个个人喜好的问题。我自己偏好递归，各位请随意。

按照这个套路，我们再来看一个例子。

例7 给定一个升序排序的数组，以及一个目标值。如果目标值在数组里，返回对应元素的下标，如果不在，返回该插入的位置。

这是LeetCode的35题。难度标记为中等（LeetCode的难度值随便看看就好，我个人觉得不太反映真实难度）。

这个题和二分查找的原型（例3）非常像：如果找到了，那么都一样返回。只不过，当最后找不到的时候，我们不是返回False，而是讨论应该把数插在哪里。但是这一点其实也不难，我们做二分查找的过程，其实就是一步步逼近那个最像的值。所以最后即使找不到目标值，该插入的位置，也就是在最后那个剩下的元素的左边或者右边了。

以下是循环的解法。

def searchInsert(A,target):
    left = 0
    right = len(A)-1
    
    while left != right:
        mid = (left+right)//2
        if target == A[mid]:
            return mid
        elif target < A[mid]:
            right = mid
        else:
            left = mid+1
            
    if target>A[left]:
        return left+1
    return left

接着是递归的解法。

def searchHelper(A,target,left,right):
    if right==left:
        if A[left] < target:
            return left+1
        return left
        
    mid = (left+right)//2
    # print mid
    if target == A[mid]:
        return mid
    elif target < A[mid]:
        return searchHelper(A,target,left,mid)
    else:
        return searchHelper(A,target,mid+1,right)

相信你都已经找到解题的模板了。

熟悉了以上的套路后，我们最后来看一题稍稍有点不同的。

例8 给定浮点数x和整数n，计算power(x,n)，即x的n次方。

这是LeetCode的50题。难度标记为中等。

很显然，我们这里禁用Python的x**n以及其它可能的库函数。

很显然的一个简单粗暴的方法是，跑n-1次循环，每次都把乘积相乘。这样我们一共需要做n-1次浮点数相乘。有没有更简单的办法？

这一题可能有点不太好想。即使你明知要用二分法，但如何二分呢？我们之前的例子，基本都有一个目标值，而我们清楚地知道这个目标值的上界和下界。而这一题里，目标值是有，但我们无从知道它的上下界，而且也无从检验一个值离目标值有多远。所以可能要换一种思路。

上面提到的暴力解法，总共要做n-1次乘法。所以如果我们要取得突破，可能的途径是减少乘法的次数。比如说，2^64，总共要63次乘法。有没有办法少做一些？

当然是有的，幂运算本身可以和低次幂进行换算。比如，2^64=(2*2)^32=4^32,接着来4^32=(4*4)^16=16^16。做完第一次换算之后，我们多做了一个乘法，但是！幂从64变成32，少了一半！，第二次之后，我们又用一次乘法，换来总乘法运算次数的减半。顺着这个思路下去，我们可以不断用一次乘法的代价，将总乘法次数减半。直到……直到不能再减，也就是n变成0或者是1。

目前为止，只有一个问题：假如n本身不能减半呢？假如是2^63呢？很简单，看成2^62*2=4^31*2=16^15*4*2。如果n是计数，就把一个x拆出来，这样n-1就是偶数了。

所以剩下的问题就不太难了：

def power(x,n):
    if n == 0:
        return 1
    elif n == 1:
        return x
    elif n < 0:
        # 这里把负数的n先变成正数，处理起来简单一些
        return pow(1.0/x,-n)
    elif n%2 == 0:
        # n是偶数
        return power(x*x,n/2)
    else:
        # n是奇数
        return power(x*x,(n-1)/2)*x

你可以看到，虽然这一题要考虑的问题多一些，但其实整个套路还是二分查找的那个样式。具体理解起来不复杂，就不啰嗦了~

下回预告

  • 哈希表
  • 排序一锅端

勘误和交流

匆忙写下的一个笔记，出错简直是一定的。如果您发现了任何错误或者有关于本文的任何建议，麻烦发邮件给我（stevenslxie at gmail.com）或者在GitHub上直接交流，不胜感激。

转载声明

如果你喜欢这篇文章，可以随意转载。但请

还有一件事

如果你阅读完这篇文章，觉得很有收获。可以：
  • 在GitHub上的这个repo打星，因为我之后还会陆续更新。这样可能方便一点，对我更是一种鼓励；
  • 如果你是V2EX过来的，可以在那里表示感谢；

    • Happy Coding!