精华内容
下载资源
问答
  • 对一个数组进行二分查找
    千次阅读 多人点赞
    2018-07-17 22:58:46


      所谓的无序数组并不是乱序,我们会遇见很多情况是旋转数组,比如一个递增数组最开始的几个元素挪到数组的最后位置。也可以理解成是两个有序数组的组合。

    面试题:打印出旋转数组的最小数字

      题目:把一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。输入一个递增排序的数组的一个旋转,输出旋转数组的最小元素。
      例如数组 {3,4,5,1,2} 为数组 {1,2,3,4,5} 的一个旋转,该数组的最小值为 1。

    方法一:

      要想实现这个需求很简单,我们只需要遍历一遍数组,找到最小的值后直接退出循环。代码实现如下:
     

     public class Test08 {
    
        public static int getTheMin(int nums[]) {
            if (nums == null || nums.length == 0) {
                throw new RuntimeException("input error!");
            }
            int result = nums[0];
            for (int i = 0; i < nums.length - 1; i++) {
                if (nums[i + 1] < nums[i]) {
                    result = nums[i + 1];
                    break;
                }
            }
            return result;
        }
    
        public static void main(String[] args) {
            // 典型输入,单调升序的数组的一个旋转
            int[] array1 = {3, 4, 5, 1, 2};
            System.out.println(getTheMin(array1));
    
            // 有重复数字,并且重复的数字刚好的最小的数字
            int[] array2 = {3, 4, 5, 1, 1, 2};
            System.out.println(getTheMin(array2));
    
            // 有重复数字,但重复的数字不是第一个数字和最后一个数字
            int[] array3 = {3, 4, 5, 1, 2, 2};
            System.out.println(getTheMin(array3));
    
            // 有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字
            int[] array4 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array4));
    
            // 单调升序数组,旋转0个元素,也就是单调升序数组本身
            int[] array5 = {1, 2, 3, 4, 5};
            System.out.println(getTheMin(array5));
    
            // 数组中只有一个数字
            int[] array6 = {2};
            System.out.println(getTheMin(array6));
    
            // 数组中数字都相同
            int[] array7 = {1, 1, 1, 1, 1, 1, 1};
            System.out.println(getTheMin(array7));
        }
    }

      打印结果没什么毛病。不过这样的方法显然不是最优的,我们看看有没有办法找出更加优质的方法处理。

    进阶,方法二:

      有序,还要查找

      找到这两个关键字,我们不免会想到我们的二分查找法,但这个数组旋转后已经不是一个真正的有序数组了,倒像是两个递增的数组组合而成的,我们可以这样思考。

      我们可以设定两个下标 low 和 high,并设定 mid = (low + high)/2(写法一)(这里有一个小点需要注意,mid=low+(high-low)/2(写法二),这个写法是更加合适的,因为在两个数都很大的情况下,low+high有存在数组越界的可能性,写法二则不会越界),下面的代码中还是按照写法一进行编程的。替换成二的话更优。
      
      我们自然就可以找到数组中间的元素 array[mid],如果中间的元素位于前面的递增数组,那么它应该大于或者等于 low 下标对应的元素,此时数组中最小的元素应该位于该元素的后面,我们可以把 low 下标指向该中间元素,这样可以缩小查找的范围。
      同样,如果中间元素位于后面的递增子数组,那么它应该小于或者等于 high 下标对应的元素。此时该数组中最小的元素应该位于该中间元素的前面。我们就可以把 high 下标更新到中位数的下标,这样也可以缩小查找的范围,移动之后的 high 下标对应的元素仍然在后面的递增子数组中。

      因为是有序数组的旋转,所以数组最后的元素一定不大于最初的元素。,所以我们的比较可以只选其中一个,代码中统一选择low所对应的元素进行比较
      不管是更新 low 还是 high,我们的查找范围都会缩小为原来的一半,接下来我们再用更新的下标去重复新一轮的查找。直到最后两个下标相邻,也就是我们的循环结束条件。

      说了一堆,似乎已经绕的云里雾里了,我们不妨就拿题干中的这个输入来模拟验证一下我们的算法。

    1. input:{3,4,5,1,2}
    2. 此时 low = 0,high = 4,mid = 2,对应的值分别是:num[low] = 3,num[high] = 2,num[mid] = 5
    3. 由于 num[mid] > num[low],所以 num[mid] 应该是在左边的递增子数组中。
    4. 更新 low = mid = 2,num[low] = 5,mid = (low+high)/2 = 3,num[mid] = 1;
      high - low ≠ 1 ,继续更新。
    5. 由于 num[mid] < num[high],所以断定 num[mid] = 1 位于右边的自增子数组中;
      更新 high = mid = 3,由于 high - low = 1,所以结束循环,得到最小值 num[high] = 1;

    Java 实现这个思路:

    public class Test08 {
    
        public static int getTheMin(int nums[]) {
            if (nums == null || nums.length == 0) {
                throw new RuntimeException("input error!");
            }
            // 如果只有一个元素,直接返回
            if (nums.length == 1)
                return nums[0];
            int result = nums[0];
            int low = 0, high = nums.length - 1;
            int mid;
            // 确保 low 下标对应的值在左边的递增子数组,high 对应的值在右边递增子数组
            while (nums[low] >= nums[high]) {
                // 确保循环结束条件
                if (high - low == 1) {
                    return nums[high];
                }
                // 取中间位置
                mid = (low + high) / 2;
                // 代表中间元素在左边递增子数组
                if (nums[mid] >= nums[low]) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            return result;
        }
    
        public static void main(String[] args) {
            // 典型输入,单调升序的数组的一个旋转
            int[] array1 = {3, 4, 5, 1, 2};
            System.out.println(getTheMin(array1));
    
            // 有重复数字,并且重复的数字刚好的最小的数字
            int[] array2 = {3, 4, 5, 1, 1, 2};
            System.out.println(getTheMin(array2));
    
            // 有重复数字,但重复的数字不是第一个数字和最后一个数字
            int[] array3 = {3, 4, 5, 1, 2, 2};
            System.out.println(getTheMin(array3));
    
            // 有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字
            int[] array4 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array4));
    
            // 单调升序数组,旋转0个元素,也就是单调升序数组本身
            int[] array5 = {1, 2, 3, 4, 5};
            System.out.println(getTheMin(array5));
    
            // 数组中只有一个数字
            int[] array6 = {2};
            System.out.println(getTheMin(array6));
    
            // 数组中数字都相同
            int[] array7 = {1, 1, 1, 1, 1, 1, 1};
            System.out.println(getTheMin(array7));
    
            // 特殊的不知道如何移动
            int[] array8 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array8));
        }
    }

    进阶,方法三:

      前面我们提到在旋转数组中,由于是把递增排序数组的前面的若干个数字搬到数组后面,因为第一个数字总是大于或者等于最后一个数字,而还有一种特殊情况是移动了 0 个元素,即数组本身,也是它自己的旋转数组。这种情况本身数组就是有序的了,所以我们只需要返回第一个元素就好了,这也是为什么我先给 result 赋值为 nums[0] 的原因。

      上述代码就完美了吗?我们通过测试用例并没有达到我们的要求,我们具体看看 array8 这个输入。先模拟计算机运行分析一下:

    1. low = 0, high = 4, mid = 2, nums[low] = 1, nums[high] = 1,nums[mid] = 1;
    2. 由于 nums[mid] >= nums[low],故认定 nums[mid] = 1 在左边递增子数组中;
    3. 所以更新 high = mid = 2,mid = (low+high)/2 = 1;
    4. nums[low] = 1,nums[mid] = 1,nums[high] = 1;
    5. high - low ≠ 1,继续循环;
    6. 由于 nums[mid] >= nums[low],故认定 nums[mid] = 1 在左边递增子数组中;
    7. 所以更新 high = mid = 1,由于 high - low = 1,故退出循环,得到 result = 1;

    但我们一眼了然,明显我们的最小值不是 1 ,而是 0 ,所以当 array[low]、array[mid]、array[high] 相等的时候,我们的程序并不知道应该如何移动,按照目前的移动方式就默认 array[mid] 在左边递增子数组了,这显然是不负责任的做法。

      我们修正一下代码:

    public class Test08 {
    
        public static int getTheMin(int nums[]) {
            if (nums == null || nums.length == 0) {
                throw new RuntimeException("input error!");
            }
            // 如果只有一个元素,直接返回
            if (nums.length == 1)
                return nums[0];
            int result = nums[0];
            int low = 0, high = nums.length - 1;
            int mid = low;
            // 确保 low 下标对应的值在左边的递增子数组,high 对应的值在右边递增子数组
            while (nums[low] >= nums[high]) {
                // 确保循环结束条件
                if (high - low == 1) {
                    return nums[high];
                }
                // 取中间位置
                mid = (low + high) / 2;
                // 三值相等的特殊情况,则需要从头到尾查找最小的值
                if (nums[mid] == nums[low] && nums[mid] == nums[high]) {
                    return midInorder(nums, low, high);
                }
                // 代表中间元素在左边递增子数组
                if (nums[mid] >= nums[low]) {
                    low = mid;
                } else {
                    high = mid;
                }
            }
            return result;
        }
    
        /**
         * 在顺序的情况下,查找数组中的最小值
         *
         * @param nums  数组
         * @param start 数组开始位置
         * @param end   数组结束位置
         * @return 找到的最小的数字
         */
        public static int midInorder(int[] nums, int start, int end) {
            int result = nums[start];
            for (int i = start + 1; i <= end; i++) {
                if (result > nums[i])
                    result = nums[i];
            }
            return result;
        }
    
        public static void main(String[] args) {
            // 典型输入,单调升序的数组的一个旋转
            int[] array1 = {3, 4, 5, 1, 2};
            System.out.println(getTheMin(array1));
    
            // 有重复数字,并且重复的数字刚好的最小的数字
            int[] array2 = {3, 4, 5, 1, 1, 2};
            System.out.println(getTheMin(array2));
    
            // 有重复数字,但重复的数字不是第一个数字和最后一个数字
            int[] array3 = {3, 4, 5, 1, 2, 2};
            System.out.println(getTheMin(array3));
    
            // 有重复的数字,并且重复的数字刚好是第一个数字和最后一个数字
            int[] array4 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array4));
    
            // 单调升序数组,旋转0个元素,也就是单调升序数组本身
            int[] array5 = {1, 2, 3, 4, 5};
            System.out.println(getTheMin(array5));
    
            // 数组中只有一个数字
            int[] array6 = {2};
            System.out.println(getTheMin(array6));
    
            // 数组中数字都相同
            int[] array7 = {1, 1, 1, 1, 1, 1, 1};
            System.out.println(getTheMin(array7));
    
            // 特殊的不知道如何移动
            int[] array8 = {1, 0, 1, 1, 1};
            System.out.println(getTheMin(array8));
    
        }
    }

      我们再用完善的测试用例放进去,测试通过。

    总结

      本题其实考察的点挺多的,实际上就是考察对二分查找的灵活运用,不少小伙伴死记硬背二分查找必须遵从有序,而没有学会这个二分查找的思想,这样会导致只能想到循环查找最小值了。
      这个是看自nanchen的公众号,加入了自己的理解写的。就舔着脸标成原创了。大佬勿怪。

    更多相关内容
  • java数组二分查找

    2015-11-02 16:56:58
    Java数组二分查找代码,将给定数组排序,然后接收键盘键入的整形数字,并查找该数字。
  • 旋转数组,如{3, 4, 5, 1, 2}是{1, 2, 3, 4, 5}的一个旋转,要求利用二分查找查找里面的数。 这是一道很有意思的题目,容易考虑不周全。这里给出如下解决方法: #include using namespace std; int sequential...
  • 主要介绍了JavaScript使用二分查找算法在数组中查找数据的方法,较为详细的分析了二分查找法的原理与javascript实现技巧,需要的朋友可以参考下
  • 给定一个 元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的第一个出现的target,如果目标值存在返回下标,否则返回 -1 示例1 输入: [1,2,4,4,5],4 返回值: 2 说明: 从左到右,...

    1.题目描述

    描述
    请实现有重复数字的升序数组的二分查找
    给定一个 元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的第一个出现的target,如果目标值存在返回下标,否则返回 -1
    示例1
    输入:
    [1,2,4,4,5],4
    返回值:
    2
    说明:
    从左到右,查找到第1个为4的,下标为2,返回2
    示例2
    输入:
    [1,2,4,4,5],3
    返回值:
    -1
    示例3
    输入:
    [1,1,1,1,1],1
    返回值:
    0

    题目链接:NC105 二分查找-II

    2.解题思路

    这一题与平常我们所写的二分查找不一样的是,实现带重复元素的数组的二分查找,且返回目标第一次出现的下标。

    我们可以先按常规二分查找实现。再在找到元素时,判断元素之前的元素是否也等于目标值。

    二分查找的递归和非递归实现可以参考:二分查找法的递归和非递归实现(C++)

    常规代码:

    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
         *
         * 如果目标值存在返回下标,否则返回 -1
         * @param nums int整型vector 
         * @param target int整型 
         * @return int整型
         */
        int search(vector<int>& nums, int target) {
            // write code here
            int low=0;
            int high=nums.size()-1;
            int half=0;
            while(low<=high){
                half=(low+high)/2;
                if(nums[half]==target)
                    return half;
                else if(nums[half]<target)
                    low=half+1;
                else
                    high=half-1;
            }
            return -1;
        }
    };
    

    只通过了部分测试用例。
    在这里插入图片描述
    接着我们上面代码基础上做改写。
    只略微改动即可。

    class Solution {
    public:
        /**
         * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
         *
         * 如果目标值存在返回下标,否则返回 -1
         * @param nums int整型vector 
         * @param target int整型 
         * @return int整型
         */
        int search(vector<int>& nums, int target) {
            // write code here
            int low=0;
            int high=nums.size()-1;
            int half=0;
            while(low<=high){
                half=(low+high)/2;
                if(nums[half]==target)
                {
                    while(nums[half]==target)
                        half--;
                    return half+1;
                }
                else if(nums[half]<target)
                    low=half+1;
                else
                    high=half-1;
            }
            return -1;
        }
    };
    

    欢迎留言评论,来个一件三连吧!

    展开全文
  • 一个数组最开始的若干个元素搬到数组的末尾,我们称之为数组的旋转。 输入一个非递减排序的数组一个旋转,输出旋转数组的最小元素。 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转,该数组的最小值为1。 又例如{...
  • 数据结构很重要,算法+数据结构+文档=程序使用PHP描述冒泡排序算法,对象可以是一个数组复制代码 代码如下://冒泡排序(数组排序)function bubble_sort($array) {$count = count($array);if ($count <= 0)return...
  • 二分查找,在一个数组有序(比如从小到大)的情况下,如果想查找某个数值是否存在于数组中,这个时候就可以使用二分查找了。具体做法就是找出数组的中间下标的元素,然后拿查找值与其比较,如果查找值小于中间元素值...

    二分查找的思想

    二分查找,在一个数组有序(比如从小到大)的情况下,如果想查找某个数值是否存在于数组中,这个时候就可以使用二分查找了。具体做法就是找出数组的中间下标的元素,然后拿查找值与其比较,如果查找值小于中间元素值,则缩小查找范围在小于中间元素的范围查找;否则,在大于中间元素值得范围查找。一直到找到查找值,或者区间缩小为0.

     

    图解:

    代码

    可以使用循环来实现,也可以使用递归。

    package com.study.algorithm.search;
    
    /**
     * @Auther: JeffSheng
     * @Date: 2019/8/27 15:57
     * @Description:
     * 二分查找
     */
    public class BinarySearch {
    
        public static int bsearch(int[] a, int n, int value) {
            int low = 0;
            int high = n - 1;
    
            while (low <= high) {
                int mid = (low + high) / 2;
                if (a[mid] == value) {
                    return mid;
                } else if (a[mid] < value) {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
    
            return -1;
        }
    
    
    
    
    
        /**
         *   二分查找的递归实现
          * @param a
         * @param n
         * @param val
         * @return
         */
        public static int bsearchRecursion(int[] a, int n, int val) {
            return bsearchInternally(a, 0, n - 1, val);
        }
    
        private static int bsearchInternally(int[] a, int low, int high, int value) {
            if (low > high){
                return -1;
            }
    
            int mid =  low + ((high - low) >> 1);
            if (a[mid] == value) {
                return mid;
            } else if (a[mid] < value) {
                return bsearchInternally(a, mid+1, high, value);
            } else {
                return bsearchInternally(a, low, mid-1, value);
            }
        }
    
    
        public static void main(String[] args) {
            int[] a={0,1,20,31,45,52,60,72,89,96};
            //循环实现
            System.out.println(bsearch(a,10,52));
            //递归实现
            System.out.println(bsearchRecursion(a,10,52));
        }
    
    }
    

     

    二分查找的时间复杂度分析

    二分查找,每次查找数据范围缩小为原来一半,假如数组元素个数为n,那么 第一次在n个数据见查找,第二次为n/2,第三次n/4,一直到范围缩小为空。n,n/2,n/4......n/2^k,k就是数据范围缩小的次数,经过k次缩小找到了数据则n/2^k=1,则k就等于logn,而每次这是比较中间值和查找值,所以二分查找的时间复杂度为O(logn).

    O(logn)的时间复杂度是非常高效的,即便2^32个数,貌似是21亿个数,对log2^32来说也不过是32次比较,所以说O(logn)的时间复杂度甚至有时比O(1)的还要高效。因为有的O(1)的常量是10000或者还要大的有限次。

     

    二分查找的应用场景

    二分查找依赖于顺序表结构。

    二分查找适合有序数据,若数据无序则需要先排序。但是数据本身需要是静态的,只需要一次排序这种就很合适,可以做到均摊时间复杂度;但如果数据本身是动态插入或者删除的则需要多次排序的时间复杂度就很高。

    二分查找不适合数据量小得的,数据量太小直接遍历就行了。

    二分查找也不适合数据量太大的,数据量太大因为是数组可能无法利用内存空间。

     

    应用:二分法查找一个正整数的平方根,要去精确到小数点后6位

    package com.study.algorithm.search;
    
    /**
     * @Auther: JeffSheng
     * @Date: 2019/8/27 16:54
     * @Description:
     * 二分法:求一个数的平方根,要求精确到小数点后6位
     */
    public class SquareRoot {
    
    
        public static double getSquareRoot(int num){
            double low=1,high=num;
            double mid = (low + high) / 2;
            while(low<=high){
                mid = (low + high) / 2;
                if(mid*mid ==num){
                    return mid;
                }else if(mid*mid < num){
                    low = mid+0.000001 ;
                }else{
                    high = mid-0.000001;
                }
            }
            return mid;
        }
    
        public static void main(String[] args) {
            double x = getSquareRoot(10);
            System.out.println(x+"----------"+x*x);
            System.out.println(Math.sqrt(10));
    
        }
    }
    

     

    展开全文
  • 原理:在使用二分查找算法之前先要确定被查找的数组必须有序的,即确定待寻找的元素的范围是[low, high],然后逐步缩小范围直到找到或找不到该元素为止。具体做法是:先取数组中间位置(mid=(low+high)/2)的数据...

    二分查找算法

    原理:在使用二分查找算法之前先要确定被查找的数组必须有序的,即确定待寻找的元素的范围是[low, high],然后逐步缩小范围直到找到或找不到该元素为止。具体做法是:先取数组中间位置(mid=(low+high)/2)的数据元素与给定值比较。若相等,则查找成功;否则,若给定值比该数据元素的值小(或大),则给定值必在数组的前半部分[low,mid-1](或后半部分[mid+1,high]),然后在新的查找范围内进行同样的查找。如此反复进行,直到找到数组元素值与给定值相等的元素或确定数组中没有待查找的数据为止。因此,二分查找每查找一次,或成功,或使查找数组中元素的个数减少一半,当查找数组中不再有数据元素时,查找失败。

    代码实现

    #include<iostream>
    #include<vector>
    using namespace std;
    
    int binarySearch(vector<int>& nums, int target) {
    	int low = 0;	// low为左边界下标
    	int high = nums.size() - 1; // high为右边界下标
    	while (low <= high)	{ // 只要low处的元素小于等于high处的元素,说明还没查找到元素,循环继续
    		int mid = (low + high) / 2; // 数组中间元素下标
    		if (nums[mid] < target) { // 当所查找的元素比中间值大,说明要查找的元素在右半区	
    			low = mid + 1;		// target在右半区,改变low的值
    		}
    		else if (nums[mid] > target) { // 当所查找的元素比中间值小,说明要查找的元素在左半区,
    			high = mid - 1;		// target在左半区,改变high的值
    		}
    		else { // 如果前面两个条件都不满足,说明已经找到target 返回mid下标位置
    			return mid;		
    		}
    	}
    	return -1;	// 当跳出循环还没有返回值,说明没找到想要的元素,返回-1
    }
    
    void print(int i) {
    	cout << i << " ";
    }
    
    int main()
    {
    	int target;
    	vector<int> nums {15, 2, 9, 36, 78, 100, 45, 8, 24, 67}; // 定义数组
    	sort(nums.begin(), nums.end());// 对数组进行排序
    	cout << "排序后数组的元素依次为: "<< endl;
    	for_each(nums.begin(), nums.end(), print);
    	cout << endl;
    	cout << "请输入你要查找的值: ";
    	cin >> target;
    	int index = binarySearch(nums, target);
    	cout << "你所找的值排序后的下标为(-1为不存在): " << index << endl;
    
    	return 0;
    }
    

    终端运行结果

    在这里插入图片描述
    在这里插入图片描述

    展开全文
  • 请实现有重复数字的升序数组二分查找: 给定一个 元素有序的(升序)整型数组 nums 和一个目标值 target ,写 一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1 示例1 输入 [1,2,4,4,5],4 ...
  • 用C语言实现有序数组二分查找

    千次阅读 多人点赞 2022-04-16 13:29:54
    C语言实现二分查找
  • 数组中的二分查找

    2022-03-24 09:31:48
    注:对于无序数组,若先进行排序,再使用二分查找。 分别有三种情况: ①当num=array[middle]时: 恭喜你,很幸运,找到了这数。 ②当num>array[middle]时: begin=middle; middle=(begin+end)/2; ③当num&...
  • 有重复数字的升序数组二分查找 题目描述 请实现有重复数字的升序数组二分查找 给定一个 元素有序的(升序)整型数组 nums 和一个目标值 target , 写一个函数搜索 nums 中的 target,如果目标值存在返回下标,...
  • 有重复数字的有序数组二分查找

    千次阅读 2021-01-13 11:29:59
    题目地址:牛客:有重复数字的有序数组二分查找 题目描述 请实现有重复数字的有序数组二分查找。 输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。 示例1 输入 ...
  • C语言——实现一个整型有序数组二分查找的两种方法
  • 无序数组二分查找

    千次阅读 2017-10-11 22:40:22
    public class 无序数组二分查找 { }
  • 数组二分查找

    千次阅读 2022-03-12 11:43:03
    二分查找 解决什么问题? 寻找数组中某一个元素 使用二分查找的前提条件是什么? 数组的有序,且元素不重复 解决问题的思路是什么? (1)设置两指针,low和high,分别指向数组的首部和尾部 (2)不断的将...
  • 有序数组二分查找

    千次阅读 2016-07-10 21:20:15
    来看第一个问题:数组二分查找。 数组是我们常见的数据结构,在程序设计中应用广泛。关于数组的操作通常是:查找、插入、删除。二分查找是我们常用的一种查找方式,效率比较高。提到二分查找,最原始的方式是线性...
  • 采用二分查找:如果数组中的数字小于下标,由于下标是-1的递减数列,但是数组中的元素差值大于等于-1,因此左边的不可能等于下标。如果数组中的数字大于下标,同理,之后的数字肯定都大于下标,往左边查找。 算法...
  • 算法系列笔记
  • 对于每进行二分查找,然后查找过程可以把某些列排除掉,这是大家都能想到的基本的思路。 比较好的另种思路是,首先选取数组右上角的数字,如果该数字等于要查找的数字,则查找结束;如果该数字大于要查找的...
  • c语言-二分查找法(数组

    千次阅读 2022-04-11 17:26:03
    pta二分查找法详解; 不足之处请见谅;
  • 有序数组和无序数组二分查找

    千次阅读 2017-04-22 10:33:37
    1. 有序数组二分查找这种情况下,也是最经常的二分查找。 已知一个已经按递增(或递减)排好序的数组,想找到某个数值为k的元素。根据下标idx查找#include #include #include using namespace std; int binary...
  • 数组下的二分查找

    千次阅读 2021-12-15 15:21:53
    相信大家对二分查找都不陌生,或者其原理大概有个了解,但是为什么很多同学对于二分查找法一看就会,一写就废? 通过几道题目,让同学们对二分查找有更深刻的认识。接下来就是深度剖析的时刻! 题目1:给定一个n...
  • 二分查找 请实现有重复数字的有序数组二分查找。 输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。 输入 5,4,[1,2,4,4,5] 输出 3(从1开始的哦。不是index) 思路: 1....
  • java代码-数组二分查找
  • 文章目录前言、代码实现、测试用例三、运行结果 前言 、代码实现 public static int binarySearch(int[] array,int key) { int left=0; int right=array.length-1; while(left<right){ int mid=...
  • 实现有序数组二分查找 C语言

    千次阅读 2018-02-20 00:16:31
    一个函数实现有序数组二分查找#include int Binarysearch(int arr[],int key,int n ) // 数组 ,关键字,数组长度。 { int left = 0; int right = n-1; int mid = 0;
  • c# 二分查找算法

    2020-09-04 22:56:26
    折半搜索,也称二分查找算法、二分搜索,是种在有序数组中查找某特定元素的搜索算法
  • js实现有序数组二分查找

    千次阅读 2021-11-22 22:32:38
    // 递归 function indexOf(arr,target,start,end){ start = start||0 end = end||arr.length-1; if(start>end){ return -1 } let mid = Math.floor((start+end)/2) if(arr[mid]>... return indexOf(arr,...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 315,927
精华内容 126,370
热门标签
关键字:

对一个数组进行二分查找