二分查找(BinarySearch)

leeon 发布于2019-08-16 13:39 / 3443人阅读

摘要：基本思想二分查找算法的基本思想就是在一个有序的默认我们都是升序，如果是降序后面的条件置反即可数组中将要查找的值和数组中间的那个元素比较如果要找的数大于中间的元素就从中间的元素后一个元素开始到数组最后一个元素这个区间里面继续寻找如果要找的数小

基本思想

二分查找算法的基本思想就是:

在一个有序的(默认我们都是升序，如果是降序后面的条件置反即可)数组中;

将要查找的值和数组中间的那个元素比较;

如果要找的数大于中间的元素,就从中间的元素后一个元素开始到数组最后一个元素这个区间里面继续寻找;

如果要找的数小于中间的元素,就从0开始到此时的中间的元素这个区间内继续寻找;

如果它们相等，那么此时我们要找的元素就是当前中间的元素，直接返回下标即可。

java代码实现

private int binarySearch(int[] arr,int k){
        int index = -1;
        int start = 0;
        int end = arr.length;
        while (start < end){
            //  这里有可能会溢出，有两种解决方案
            //  1、 修改为 start+(end-start)/2
            //  2、 通过位移操作，这样也可以完成除2，在jdk源码中使用的是这种方法
            int mid = (end + start) / 2;
            //  如果小于中间的元素就从0开始到当前中间的下标这个区间里面继续寻找
            if (k < arr[mid]){
                end = mid;
            //  如果大于中间的元素就从当前的下标到最后一个元素这个区间里面继续寻找
            }else if (k > arr[mid]){
                start = mid + 1;
            //  如果等于中间的元素就说明当前元素就是我们要找的下标
            }else {
                return mid;
            }
        }
        //  如果循环结束了都没找到说明这个数组里面没有我们要找的元素
        return -1;
    }

时间复杂度分析

最好的情况是我们要找的就是中间那个,此时的时间复杂度为O(1);

最坏的情况是我们找完最后一趟才找到甚至没有找到,这个时候的时间复杂度为O(logN);

GPU云服务器云服务器二分查找二分查找代码二分法查找二分查找c语言实例

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

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

数据结构与算法：二分查找

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

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
【程序员必会十大算法】之二分查找算法

摘要：递归实现不考虑相同数二分查找，不考虑有相同数的情况递归找到了考虑有相同数二分查找考虑有相同元素的情况递归要查找的值 1.递归实现 ①不考虑相同数 /** * 二分查...

YFan 2021-09-24 09:48 评论0 收藏0
查找算法之二分查找法

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

Jochen 2019-08-15 17:44 评论0 收藏0