查找算法之二分查找法

Jochen 发布于2019-08-15 17:44 / 394人阅读

摘要：查找算法之二分查找法思想二分查找法的思想非常简单，对于一个有序数列，找它中间的元素，看是否是查找目标，如果不是，就看这个查找目标是小于还是大于中间元素，然后在对应的区间内重复上述过程。

查找算法之二分查找法 思想

二分查找法的思想非常简单，对于一个有序数列，找它中间的元素，看是否是查找目标，如果不是，就看这个查找目标是小于还是大于中间元素，然后在对应的区间内重复上述过程。

算法

需要注意几个问题：

while 循环：while 循环的条件应该是 left < right 还是 left <= right 呢？

这可以从我们设置的左右边界判断出来，我们设置的 left = 0, right = n - 1，因此 [left, right] 是一个闭区间，那么当 left = right 时，[left, right] 区间同样满足我们的设置，因此，这个循环内应该是 left <= right。

target 和 arr[mid] 的判断：当 target > arr[mid] 时，是应该 left = mid 还是 left = mid + 1 呢？

这和在 while 中的判断是一个思路，当 target > arr[mid] 时，target 在 [mid + 1, r] 中，而非 [mid, r]，因为显然此时 mid　已经不可能等于 target 了，因此我们不需要再比较 target 和 arr[mid]。

同样地，当 target < arr[mid] 时，也是类似的判断。

循环不变量：left 和　right 的定义十分重要，因为在后面我们要不断地维护这个定义，我们必须要保证是在 [left, right] 这个区间里寻找　target，这也就是 循环不变量，意思就是 left 和 right 的值虽然一直在变化，但是有一个声明 在 [left, right] 区间内寻找 target 是永远不变的，只要我们维护住这个 循环不变量，那么就可以保证我们的算法是正确的。当然，这里你也可以定义成 left = 0, right = n，即[left, right)，那么此时定义就发生了变化，相应地，在 while 中为了维护这个定义，我们需要把条件改成 left < right，因为当 left = right 时，显然 [left, right)是错误的，后面再查找时也要做相应的修改。

    private int binarySearch(T arr[], int n, T target) {

        int left = 0, right = n - 1; // 在 [left, right] 区间内寻找 target
        
        while (left <= right) { // 当 left = right 时，区间 [left, right] 仍然有效
            int mid = (left + right) / 2;
            if (arr[mid] == target)
                return mid;
            if (target > arr[mid])
                left = mid + 1; // target 在 [mid+1, r] 中
            else
                right = mid - 1; // target 在 [left, mid - 1] 中
        }

        return -1;
    }

不知道到这里大家有没有发现一个 bug

因为 left 和 right 都是 int，所以当值足够大时，在计算 mid = (left + right) / 2 时可能会发生整型溢出！

因此，为了避免这个问题，我们使用减法来计算。

完全正确的二分查找法

    public int binarySearch(T[] arr, int n, T target) {

        int left = 0, right = n - 1; // 在 [left, right] 区间内寻找 target

        while (left <= right) { // 当 left = right 时，区间 [left, right] 仍然有效
            int mid = left + (right - left) / 2;
            if (arr[mid].compareTo(target) == 0)
                return mid;
            if (target.compareTo(arr[mid]) > 0)
                left = mid + 1; // target 在 [mid+1, r] 中
            else
                right = mid - 1; // target 在 [left, mid - 1] 中
        }

        return -1;
    }

测试

我们可以写一个 Util 来帮助我们生成测试用例

ArrayUtil.java

    public static Integer[] generateSortedArray(int n) {

        assert n > 0;

        Integer[] arr = new Integer[n];
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }

        return arr;
    }

BinarySearch.java

    public static void main(String[] args) {

        BinarySearch bs = new BinarySearch();
        int n = (int)Math.pow(10, 7); // 用 10,000,000 数据测试
        Integer[] data = ArrayUtil.generateSortedArray(n);

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < n; i++)
            if (i != bs.binarySearch(data, n, i))
                throw new IllegalStateException("find i failed");
        long endTime = System.currentTimeMillis();

        System.out.println("Binary Search success!");
        System.out.println("Time cost: " + (endTime - startTime) + "ms");
    }

完整代码：github: My-Notes/algorithm（Java）/01-binarySearch/src/

云服务器 GPU云服务器二分查找法c语言程序二分查找二分查找代码二分法查找

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/69408.html

二分查找

摘要：正文二分查找关于二分查找法二分查找法主要是解决在一堆数中找出指定的数这类问题。用二分查找法找寻上界与精确查找不同之处在于，精确查找分成三类大于，小于，等于目标数。由一道题目引出的：题目描述给定一个有序的数组，查找某个数是否在数组中，请编程实现。分析与解法一看到数组本身已经有序，我想你可能反应出了要用二分查找，毕竟二分查找的适用条件就是有序的。那什么是二分查找呢？二分查找可以...

jerryloveemily 2019-08-20 14:48 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

zsirfs 2019-08-23 15:33 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

you_De 2019-08-16 15:26 评论0 收藏0
数据结构与算法：二分查找

摘要：为检查长度为的列表，二分查找需要执行次操作。最后需要指出的一点是高水平的读者可研究一下二叉树关于二叉树，戳这里数据结构与算法二叉树算法常见练习在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。常见数据结构简单数据结构（必须理解和掌握）有序数据结构：栈、队列、链表。有序数据结构省空间（储存空间小）无序数据结构：集合、字典、散列表，无序...

gotham 2019-07-31 10:07 评论0 收藏0
LeetCode 之 JavaScript 解答第69题 —— X 的平方根（Squrt(x)）

摘要：测试用例输入输入输入负数的输入平方根为正整数的输入平方根为小数的代码实现写二分查找代码需要注意的三点循环退出条件。使用二分查找之前，判断问题是否满足二分查找的要求。 Time：2019/4/17Title: sqrt(x)Difficulty: EasyAuthor: 小鹿题目：sqrt(x) Implement int sqrt(int x). Compute and retu...

sf_wangchong 2019-08-23 17:00 评论0 收藏0