二分查找法_二分查找法时间复杂度 - CSDN
精华内容
参与话题
  • 二分查找法

    2020-02-28 22:36:16
    一、需查找和目标值相等的数 比如数组 [2, 4, 5, 6, 9],target = 6,...二分查找法的代码如下: int find(int[] nums, int target) { int left = 0, right = nums.length; while (left < right) { int mi...

    一、需查找和目标值相等的数

    比如数组 [2, 4, 5, 6, 9],target = 6,返回3,即target 的在数组中的位置。二分查找法的代码如下:

    int find(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) return mid;
            else if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return -1;
    }

    注意二分查找法的写法并不唯一,主要可以变动地方有四处:

    第一处是 right 的初始化,可以写成 nums.length或者 nums.length- 1。

    第二处是 left 和 right 的关系,可以写成 left < right 或者 left <= right。

    第三处是更新 right 的赋值,可以写成 right = mid 或者 right = mid - 1。

    第四处是最后返回值,可以返回 left,right,或 right - 1。

    但是这些不同的写法并不能随机的组合,像博主的那种写法,若 right 初始化为了 nums.length,那么就必须用 left < right,而最后的 right 的赋值必须用 right = mid。但是如果我们 right 初始化为 nums.length - 1,那么就必须用 left <= right,并且right的赋值要写成 right = mid - 1,不然就会出错。

     

    二、查找第一个不小于目标值的数

          如果查找的目标值不一定会在数组中出现,也有可能是跟目标值相等的数在数组中并不唯一,而是有多个,那么这种情况下 nums[mid] == target 这条判断语句就没有必要存在。比如在数组 [2, 4, 5, 6, 9] 中查找数字3,就会返回数字4的位置;在数组 [0, 1, 1, 1, 1] 中查找数字1,就会返回第一个数字1的位置,即返回的位置就是 right 指针指向的地方。代码如下:

    int find(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] < target) left = mid + 1;
            else right = mid;
        }
        return right;
    }

        如果变为查找最后一个小于目标值的数,因为已经找到了第一个不小于目标值的数,那么再往前退一位,返回 right - 1,就是最后一个小于目标值的数。

     

    三、 查找第一个大于目标值的数

          这里跟第二种写法上很相似,只需要添加一个等号,将之前的 nums[mid] < target 变成 nums[mid] <= target,这变化其实直接就改变了搜索的方向,使得在数组中有很多跟目标值相同的数字存在的情况下,返回最后一个相同的数字的下一个位置。

    int find(int[] nums, int target) {
        int left = 0, right = nums.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] <= target) left = mid + 1;
            else right = mid;
        }
        return right;
    }

    与第二种一样,可以变形为查找最后一个不大于目标值的数。

     

     

    展开全文
  • 二分查找法(折半查找法):查找数组中是否包含指定元素。如果包含指定元素,则返回指定元素的index(从0开始);如果不包含指定元素,则返回-1; 前提:数组中的元素必须是有序的。 原理: 将被查找的数组分为...

            二分查找法(折半查找法):查找数组中是否包含指定元素。如果包含指定元素,则返回指定元素的index(从0开始);如果不包含指定元素,则返回-1;

            前提:数组中的元素必须是有序的。

          原理:

            将被查找的数组分为三部分,依次是中值前、中值、中值后,将指定元素和数组的中值进行比较,如果指定元素小于中值则在(中值前)中找,如果指定元素大于中值则在(中值后)中找,如果指定元素等于中值则直接返回。依次查找后,如果不包含指定元素,则返回-1;

                      注:中值即数组中间位置的值。

            原生方法:Arrays.sort(a);:对a数组进行升序排序。

                             Arrays.binarySearch(a,b);:使用二分法查找a数组中是否包含b这个元素。

     

         两种方式:循环实现和递归实现

    /**
         * 循环实现
         * 二分查找法(折半查找法):查找数组中是否包含指定元素。
         * 前提:数组中的元素必须是有序的。
         * Arrays.sort(a);:对a数组进行升序排序。
         * Arrays.binarySearch(a,b);:使用二分法查找a数组中是否包含b这个元素。
         *
         * @param arr 被查找的数组
         * @param key 指定元素
         * @return 如果包含指定元素,则返回指定元素的index(从0开始);如果不包含指定元素,则返回-1;
         */
        public static int binarySearch(int[] arr, int key) {
            int min = 0;
            int max = arr.length - 1;
    
            while (min <= max) {
                int mid = (min + max) >> 1;//(min + max)/2
    
                if (arr[mid] > key) {
                    max = mid - 1;
                } else if (arr[mid] < key) {
                    min = mid + 1;
                } else {
                    return mid;
                }
            }
    
            return -1;
        }
    
        /**
         * 递归实现
         * 二分查找法(折半查找法):查找数组中是否包含指定元素。
         * 前提:数组中的元素必须是有序的。
         * Arrays.sort(a);:对a数组进行升序排序。
         * Arrays.binarySearch(a,b);:使用二分法查找a数组中是否包含b这个元素。
         *
         * @param arr 被查找的数组
         * @param key 指定元素
         * @return 如果包含指定元素,则返回指定元素的index(从0开始);如果不包含指定元素,则返回-1;
         */
        public static int binarySearch(int[] arr, int key, int startIndex, int endIndex) {
            if (startIndex > endIndex || startIndex < 0 || endIndex > arr.length - 1) {
                return -1;
            }
    
            int midIndex = (startIndex + endIndex) >> 1;//(startIndex + endIndex)/2
    
            if (arr[midIndex] > key) {
                return binarySearch(arr, key, startIndex, midIndex - 1);
            } else if (arr[midIndex] < key) {
                return binarySearch(arr, key, midIndex + 1, endIndex);
            } else {
                return midIndex;
            }
        }

          验证:

            //验证自定义的二分查找法
            int[] a = {};
            int[] b = {1, 2, 3, 4, 5, 6, 7, 8, 9};
            int[] c = {1, 4, 6, 7, 8, 3, -2};
    
            //循环实现
            int circulate1 = binarySearch(a, 0);
            int circulate2 = binarySearch(b, 5);
            int circulate3 = binarySearch(c, -2);
            Arrays.sort(c);
            int circulate4 = binarySearch(c, -2);
            LogUtil.e("++++++++++++++++", circulate1 + "");  //-1
            LogUtil.e("++++++++++++++++", circulate2 + ""); //4
            LogUtil.e("++++++++++++++++", circulate3 + ""); //-1
            LogUtil.e("++++++++++++++++", circulate4 + ""); //0
    
            //递归实现
            int recursion1 = binarySearch(a, 0, 0, a.length - 1);
            int recursion2 = binarySearch(b, 5, 0, b.length - 1);
            int recursion3 = binarySearch(c, -2, 0, c.length - 1);
            LogUtil.e("++++++++++++++++", recursion1 + "");  //-1
            LogUtil.e("++++++++++++++++", recursion2 + ""); //4
            LogUtil.e("++++++++++++++++", recursion3 + ""); //0

    ---------------------------------------------------------------------------------------------------------------------------

    早计划,早准备,早完成。 欢迎关注!交流!Star!

    GitHub:https://github.com/wangyang0313

    微信公众号:一个灵活的胖子MrWang

    简书:https://www.jianshu.com/u/e5e733d79b96  

    展开全文
  • 二分查找算法(递归与非递归两种方式)

    万次阅读 多人点赞 2017-12-21 17:56:32
    首先说说二分查找法二分查找法是对一组有序的数字中进行查找,传递相应的数据,进行比较查找到与原数据相同的数据,查找到了返回1,失败返回对应的数组下标。 采用非递归方式完成二分查找法。java代码如下所示。

    首先说说二分查找法。

    二分查找法是对一组有序的数字中进行查找,传递相应的数据,进行比较查找到与原数据相同的数据,查找到了返回对应的数组下标,没有找到返回-1;

    如下示例,其中有序数组中, 是按照从小到大的顺序排列的。(再次感谢网友的指出)


    采用非递归方式完成二分查找法。java代码如下所示。

    /**
         * 二分查找普通实现。
         * @param srcArray 有序数组
         * @param key 查找元素
         * @return  不存在返回-1
         */
        public static int binSearch(int srcArray[], int key) {
            int mid;
            int start = 0;
            int end = srcArray.length - 1;
            while (start <= end) {
                mid = (end - start) / 2 + start;
                if (key < srcArray[mid]) {
                    end = mid - 1;
                } else if (key > srcArray[mid]) {
                    start = mid + 1;
                } else {
                    return mid;
                }
            }
            return -1;
        }


    采用递归方式完成二分查找算法。代码如下所示。

    /**
         * 二分查找递归实现。
         * @param srcArray  有序数组
         * @param start 数组低地址下标
         * @param end   数组高地址下标
         * @param key  查找元素
         * @return 查找元素不存在返回-1
         */
        public static int binSearch(int srcArray[], int start, int end, int key) {
            int mid = (end - start) / 2 + start;
            if (srcArray[mid] == key) {
                return mid;
            }
            if (start >= end) {
                return -1;
            } else if (key > srcArray[mid]) {
                return binSearch(srcArray, mid + 1, end, key);
            } else if (key < srcArray[mid]) {
                return binSearch(srcArray, start, mid - 1, key);
            }
            return -1;
        }


    递归思想会被经常用到,更加突出了编程解决问题的高效。

    调用执行main函数,代码如下。

     public static void main(String[] args) {
            int srcArray[] = {3,5,11,17,21,23,28,30,32,50,64,78,81,95,101};
            System.out.println(binSearch(srcArray, 0, srcArray.length - 1, 222));
            System.out.println(binSearch(srcArray,81));
        }


    在这里说声抱歉,之前的代码有问题,自己一直没有修改,罪过罪过



    展开全文
  • 算法(一):二分查找法

    千次阅读 2018-07-23 13:23:48
    O(log n),也叫对数时间复杂度,这样的算法包括二分查找。 O(n),也叫线性阶时间复杂度,这样的算法包括简单查找。 O(n * log n), (n*对数复杂度) O(n^2),平方阶时间复杂度 O(n!),阶乘阶时间复杂...

    算法基础:

    一、大O表示法:

    指示算法的速度有多快,用于指出随数量的增大,算法的所需步骤增加的速度,常见的大O运行时间(时间复杂度):
    O(1)表示常数阶时间复杂度
    O(log n),也叫对数时间复杂度,这样的算法包括二分查找。
    O(n),也叫线性阶时间复杂度,这样的算法包括简单查找。
    O(n * log n), (n*对数复杂度)
    O(n^2),平方阶时间复杂度
    O(n!),阶乘阶时间复杂度
    复制代码

    n越来越大时,算法效率图解:

     

     

     

    要点

    • 1.二分查找法只适用于从有序的队列中进行查找(比如数字和字母等),将队列排序后再进行查找

    • 2.二分查找法的运行时间为对数时间O(㏒₂n) ,即查找到需要的目标位置最多只需要㏒₂n步,假设从[0,99]的队列(100个数,即n=100)中寻到目标数30,则需要查找步数为㏒₂100 , 即最多需要查找7次( 2^6 < 100 < 2^7)

    • 3.简单查询(遍历查询)的运行时间为线性时间O(n), 假设从[0,99]的队列中(n=100)寻到目标数30,则最多需要查找步数为100步

    • 4.对于容器内数量很少的情况下,2种查找也许没啥差别,当数量大的情况下,差别就很大,比如假设查找比较步骤一次需要1秒,当容量数目为100000时,O(n)需要100000秒即约27.8小时,而logn只需要 2^16 < 100000 < 2^17,即17秒,这差距非常的大

    • 5.时间复杂度都是针对最坏的情况所表示的,表示最多需要多少步

    案例

    从1~99的容器内,找出指定的数字;

    java实现:
    A:简单查找法,即遍历查找,全部遍历直到找到指定的数便停止
    
    /**
     * 简单查找
     * @param array    传入存放全部数据的容器
     * @param target   需要查找的目标数
     * @return
     */
    public Integer search(Integer[] array,int target){
        for(int i=0;i<array.length;i++){
            if(array[i] == target){
                return i;
            }
        }
        return null;
    }
    
    B:二分查找法
    
    /**
     * 二分查找法
     * @param array   传入存放全部数据的容器
     * @param target  需要查找的目标数
     * @return
     */
    public Integer searchDichotomy(Integer[] array, int target){
        int low =0;
        int hight=array.length-1;
        while(low<=hight){                 //遍历还没结束
            int mid = (low+hight)/2;       //取中间值mid点位置
            if(array[mid]==target){        //寻找到目标数
                return mid;
            }
            if(array[mid] > target){        //如果中间值大于目标数,则将highr点位置移动mid位置左边
               hight = mid-1;
            }
            if(array[mid] < target){       //如果中间值小于目标数,则将low点位置移动mid位置右边
                low = mid+1;
            }
        }
        return null;
    }
    复制代码

    图解:

    假设容器中为[1,99],共99个数 必须明白因为时间复杂度是针对最坏情况的,二分查找所需最多为7步,简单遍历法最多为99步(当查找的是数99);

    根据实际需要查找的数,所消耗的步骤不一定一样,但都不会超过时间复杂度

    步骤图解如下所示([1,99],即n=99,查找的数为30):

     

     

     

    时间复杂度推算过程:

    参考:https://blog.csdn.net/frances_han/article/details/6458067 二分查找的基本思想是将n个元素分成大致相等的两部分,去a[n/2]与x做比较,如果x=a[n/2],则找到x,算法中止;如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x. 时间复杂度无非就是while循环的次数! 总共有n个元素, 渐渐跟下去就是n,n/2,n/4,....n/2^k,其中k就是循环的次数 由于你n/2^k取整后>=1 即令n/2^k=1 可得k=log2n,(是以2为底,n的对数) 所以时间复杂度可以表示O()=O(logn)

    有兴趣共同进步可以扫描关注微信订阅号

     

    展开全文
  • Java算法之二分查找法

    2019-04-22 22:12:18
    什么是二分查找法 二分查找法也叫折半查找法,是一种效率比较高的查找方法,它要求被查找的数组是有序的。 二分查找原理 案例:大家应该都玩过猜数字游戏吧,比如我们要从1到100找出某一个数,一般我们会...
  • 作者最近突然想到了二分查找法,今天进拿出来跟大家分享一下 二分查找法顾名思义就是把列表分成两份进行查找,即先定义个最小下标start=0和一个最大下标end = len(list),然后通过相加对2求余或者除以2在转换为int...
  • 【算法图解】 之 [二分查找法] 详解

    千次阅读 2019-07-22 16:08:18
    入门算法学习,看的第一本是深入浅出的《算法图解》一书,本博客是对《算法图解》一书的学习笔记,将书中的分享的算法示例用Python3语言实现。 ...或者也可以留言你的邮箱...二分查找是一种算法,其输入是一个有序的元...
  • 二分查找算法(C语言实现)

    万次阅读 2018-03-19 15:48:27
    二分查找
  • 关键字与左右标的大小比较#include int main() { int arr[] = { 0, 1, 2, 3, 4, 6, 7, 9 }; int left = 0; int right = sizeof(arr) / sizeof(arr[0])-1; int mid = 0; int key = 4;... while (le
  • java实现二分查找-两种方式

    万次阅读 多人点赞 2017-10-09 01:14:27
    二分查找是一种查询效率非常高的查找算法。又称折半查找。 起初在数据结构中学习递归时实现二分查找,实际上不用递归也可以实现,毕竟递归是需要开辟额外的空间的来辅助查询。本文就介绍两种方法 二分查找算法...
  • 二分查找”算法的时间复杂度

    万次阅读 多人点赞 2016-08-29 14:13:55
    算法的时间复杂度无非就是for、while等包含起来的基本运算单元的循环次数1、二分查找二分查找(binary search),也称作折半查找(half-interval search),每次划分一半进行下一步搜索,所以时间复杂度无非就是...
  • 二分查找法过程详解

    万次阅读 2017-04-13 15:56:19
    首先第一要素需要明白,二分查找法适用于有序数组,记住,二分查找之前一定要排序!!! 二分查找元素代码:int base=0; int top=size-1; while(base){ mid=(top+base)/2; if(v[mid]==target) break; //mid为所求下标 if...
  • Java二分查找法

    千次阅读 2018-07-02 16:06:52
    含义: 二分查找又称折半查找,一种效率较高的查找方法条件: 1、必须为顺序存储结构;2、必须按关键字大小有序排列;原理: 例:int arrays[]={2,8,10,16,64,512,1024}; 1、将有序数组分为三个部分,分别为中间...
  • 【C/C++】折半查找(二分查找

    万次阅读 2016-07-02 21:41:45
    一、二分查找 在C和C++里,二分查找是针对有序数组所用的一种快速查找元素的方法。 二、二分查找的条件以及优缺点 条件:针对有序数组(元素从小到大或从大到小) 优点:查询速度较快,时间复杂度为O(n) 缺点:有...
  • 二分查找法和顺序查找法

    千次阅读 2011-02-16 10:53:00
    二分查找1、二分查找(Binary Search) 二分查找又称折半查找,它是一种效率较高的查找方法。 二分查找要求:线性表是有序表,即表中结点按关键字有序,并且要用向量作为表的存储结构。不妨设有序表是递增有序的。2...
  • 递归实现二分查找

    千次阅读 2018-01-10 14:27:10
    使用递归实现二分查找 public class Test { public static void main(String[] args) { //数组 int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }; //要查找的元素 int key = 1; //第一个元素的下标 int low...
  • 查找算法之二分查找的C++实现

    千次阅读 2018-04-03 09:55:43
    二分查找 二分查找算法,说白了就是在有序的数组里面给予一个存在数组里面的值key,然后将其先和数组中间的比较,如果key大于中间值,进行下一次mid后面的比较,直到找到相等的,就可以得到它的位置。 前提...
  • C语言二分法查找法

    万次阅读 多人点赞 2019-10-17 10:58:16
    所谓的二分查找法,其实是一种有序的查找方法,也称折半查找(Binary Search),如果是无序的则要先进行排序操作。基本思想是:目标值通过与中间元素比较,可分为三种情况: 第一种情况:目标值与中间元素相等,...
  • 二分查找(C++)+递归和非递归算法

    万次阅读 2013-08-31 17:09:14
    关于二分查找法 二分查找法主要是解决在“一堆数中找出指定的数”这类问题。 而想要应用二分查找法,这“一堆数”必须有一下特征: 存储在数组中 有序排列 所以如果是用链表存储的,就无法在其上应用...
  • C语言中折半查找法(二分法)的实现

    万次阅读 多人点赞 2019-04-09 20:42:33
    折半查找法也叫做二分查找,顾名思义,就是把数据分成两半,再判断所查找的key在哪一半中,再重复上述步骤知道找到目标key; 注意:(咳咳,敲黑板)折半查找法仅适用于对已有顺序的数组、数据进行操作!!! 很...
1 2 3 4 5 ... 20
收藏数 137,219
精华内容 54,887
关键字:

二分查找法