算法系列之七 二分查找

二分查找是一个较为简单的算法。用于在排好序的序列中进行查找。二分查找是典型的“分治算法”,其复杂度是 $O(\log n)$。

虽然说算法简单,但是很多人都不能无任何参考的情况下,写出来。所以,还是有必要理解记忆一下算法的细节。

二分查找的中心思想是:

  1. 将序列分为两个子序列
  2. 找到序列中的中间元素比较
  3. 如果大于中间元素,则将 右边子序列当做原始序列,从 第一步开始重复
  4. 如果小于中间元素,则将 左边子序列当做原始序列,从 第一步开始重复
  5. 如果相等,结束算法

二分查找可以使用递归实现,但因为是 尾递归,也可以转为循环实现。

使用循环的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int binary_search(int v, const int *a, int lo, int hi) {

while (lo <= hi) {

int mid = (lo + hi) >> 1;

if (v < a[mid]) hi = mid - 1;

else if (v > a[mid]) lo = mid + 1;

else return mid;

}

return -1;
}

递归的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int binary_search_recursion(int v, const int *a, int lo, int hi) {

if (lo > hi) // 递归退出条件,重要
return -1;

int mid = (lo + hi) >> 1;

if (v < a[mid])
return binary_search_recursion(v, a, lo, mid - 1);

else if (v > a[mid])
return binary_search_recursion(v, a, mid+1, hi);

else
return mid;

}
reposkeeper wechat
关注微信公众号