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

Question

查找（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

你可以看到，虽然这一题要考虑的问题多一些，但其实整个套路还是二分查找的那个样式。