算法系列之七 二分查找

  • 2018-06-03
  • 240
  • 0

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

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

二分查找的中心思想是:

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

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

使用循环的版本

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;
}

递归的版本

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) 授权分享 By CC BY-SA 4.0 Creative Commons License

关注微信公众号,获取新文章的推送!
qrcode

评论

还没有任何评论,你来说两句吧

发表评论

*

code