二分法和三分法

发表于 更新于 分类于 阅读次数： 本文字数： 671 阅读时长 ≈ 2 分钟
Look before you leap.

二分法

简单介绍：

  • 在计算机科学中，二分查找算法(Binary Search Algorithm)，也称折半搜索算法(Half-interval Search Algorithm)、对数搜索算法(Logarithmic Search Algorithm)，是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。

  • 二分查找算法在最坏情况下是对数时间复杂度的，需要进行 二分查找算法使用常数空间，对于任何大小的输入数据，算法使用的空间都是一样的。除非输入数据数量很少，否则二分查找算法比线性搜索更快，但数组必须事先被排序。尽管一些特定的、为了快速搜索而设计的数据结构更有效（比如哈希表)，二分查找算法应用面更广。

  • 二分查找算法有许多种变种。比如分散层叠可以提升在多个数组中对同一个数值的搜索的速度。分散层叠有效的解决了计算几何学和其他领域的许多搜索问题。指数搜索将二分查找算法拓宽到无边界的列表。二叉搜索树和B树数据结构就是基于二分查找算法的。

需要满足条件：

  1. 满足两段性
  2. 满足单调性，在某些特殊情况下，这个条件是不必要的

算法实现：

根据数据类型的不同，我们可以将二分查找分为以下两种

  • 整数二分
  • 浮点数二分

整数二分：

区间[l, r]被划分为[l, mid]和[mid + 1, r]

1
2
3
4
5
6
7
8
9
10
11
int Binary_Search(int l, int r) {
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid)) {
            r = mid;
        } else {
            l = mid + 1;
        }
    }
    return l;
}

区间[l, r]被划分为[l, mid - 1]和[mid, r]

1
2
3
4
5
6
7
8
9
10
11
int Binary_Search(int l, int r) {
    while (l < r) {
        int mid = l + r + 1 >> 1;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid - 1;
        }
    }
    return l;
}

浮点数二分：

1
2
3
4
5
6
7
8
9
10
11
12
double Binary_Search(double l, double r) {
    const double EPS = 1E-6;
    while (r - l > EPS) {
        double mid = (l + r) / 2;
        if (check(mid)) {
            l = mid;
        } else {
            r = mid;
        }
    }
    return l;
}

稳定性及时间复杂度分析

  • 二分查找是一种稳定的算法

  • 二分的时间复杂度为

三分法