精华内容
下载资源
问答
  • 什么是二分查找?首先,二分查找也叫折半查找,它是对于一组有序(升序或降序)数列来说的,我们举例子说明这个思想。 例如:猜数字游戏 随机给出1-100内的一个数字,请猜出这个数字 那我们不能随机没有规律的去...

    什么是二分查找?

    首先,二分查找也叫折半查找,它是对于一组有序(升序或降序)数列来说的,我们举例子说明这个思想。
    例如:猜数字游戏
    随机给出1-100内的一个数字,请猜出这个数字
    那我们不能随机没有规律的去猜,这时考虑二分查找的思想
    例如38
    第一次猜50,告诉你猜大了,那么此时就在1-50内折半
    第二次猜25,告诉你猜小了,那么此时就在26-49内折半…以此类推
    这就是二分查找的思想。

    那么我们如何用c语言来编写实现它呢?

    给出一个升序数组arr[10]={0,1,2,3,4,5,6,7,8,9},要求用二分查找的方法找出4。
    那么第一次我们折半找到5,5>4
    然后进行第二次折半找到2,2<4
    进行第三次折半找到3,3<4
    最后一次我们就找到了目标数字4

    接下来我们用两种方式实现:

    1、(此代码存在安全问题并可以优化)

    #include<stdio.h>
    int binary_search(int arr[], int num, int sz)//二分查找函数
    {
        int mid = 0;//折半后数字的下标
        int left = 0;//左下标
        int right = sz - 1;//右下标
        while (left <= right)//判断当左下标小于右下标条件满足
        {
            mid = (left + right)/2;//找出折半后数字下标(尽量不要用此方法)
            if (num <arr[mid])
                right = mid;
            else if (num > arr[mid])
                left = mid;
            else
                return mid;//找到目标数字并返回数组下标
        }
        return -1;//左下标大于右下标没找到
    }
    int main()
    {
        int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int num = 3;
        int sz = sizeof(arr) / sizeof(arr[0]);//求这个数组的大小
        int tmp = binary_search(arr,num,sz);
        if (tmp != -1)
            printf("exist the number is:%d", tmp);
        else
            printf("no exist!");
        return 0;
    }

    2、这个代码更具体是代码一的优化 给出左右下标在这个范围内查找

    #include<stdio.h>
    int binary_search(int arr[], int left, int right, int  num)//二分查找函数 给出做右下标在此范围内找
    {
        int mid = 0;
        while (left <= right)
        {
            mid = left + ((right - left) >> 1);//这样求中间的数的下标等安全>>为右移符号,右移1等于除以2
            if (num <arr[mid])
                right = mid;
            else if (num > arr[mid])
                left = mid;
            else
                return mid;
        }
        return -1;
    }
    
    int main()
    {
        int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
        int num = 3;
        int tmp = binary_search(arr, 0, 6, num);
        if (tmp!=-1)
            printf("exist the number is:%d", tmp);
        else
            printf("no exist!");
        return 0;
    }
    展开全文
  • 主要介绍了C++实现旋转数组二分查找方法,涉及数组的操作,有值得借鉴的技巧,需要的朋友可以参考下
  • 无序数组二分查找

    千次阅读 2017-10-11 22:40:22
    public class 无序数组二分查找 { }
    public class 无序数组二分查找 {
        public static int quickSortOneTime(int[] a, int i, int j)// 一趟快速排序
        {
            int high, low, key;
            high = j;
            low = i;
            key = a[low];
            while (low < high) {
                while (key <= a[high] && low < high) {
                    high--;
                }
    
                if (low < high) {
                    a[low] = a[high];
                    low++;
                }
                while (key >= a[low] && low < high) {
                    low++;
                }
                if (low < high) {
                    a[high] = a[low];
                    high--;
                }
            }
            a[high] = key;
            return high;
    
        }
    
        public static void twoDepart(int[] a, int i, int j, int values) {
            int mid = quickSortOneTime(a, i, j);
            System.out.println("mid = " + mid + " i = " + i + " j = " + j);
            System.out.println(i < j);
            if (i < j) {
                if (a[mid] == values) {
                    System.out.println("ok, keyword is at " + mid);
    
                } else if (a[mid] < values) {
                    i = mid + 1;
                    twoDepart(a, i, j, values);
                } else if (a[mid] > values) {
                    j = mid - 1;
                    twoDepart(a, i, j, values);
                }
            } else if (i == j && a[mid] != values) {
                System.out.println("It doesn't exists");
            } else
                System.out.println("Finalily we find the keyword is at   " + mid);
    
        }
    
        public static void main(String[] args) {
            int[] a = new int[] { 1, 4, 9, 3, 24, 21, 6, 9, 9, 7, 6, 5, 3 };
            int values = 4;
            twoDepart(a, 0, a.length - 1, values);
        }
    }
    展开全文
  • 逆天!无序数组使用二分查找

    千次阅读 多人点赞 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的公众号,加入了自己的理解写的。就舔着脸标成原创了。大佬勿怪。

    展开全文
  • matlab实现有序数组二分查找

    千次阅读 2019-06-25 15:37:17
    对于一个有序的列表或数组对二分查找的方式进行元素查找 function [result_index] = binary_search(array,element) %array 有序数组 %element 查找元素 %result_index 输出下标 low = 1; %设置数组下标 high = ...

    %二分查找法
    %设计思想;对于一个有序的列表或数组,对二分查找的方式进行元素查找
    function [result_index] = binary_search(array,element)
    %array 有序数组
    %element 查找元素
    %result_index 输出下标

    low = 1; %设置数组下标
    high = length(array);%设置数组上标
    
    %进行二分查找
    %使用选择多分支语句
    
    while low <= high      %设定查找终止条件
        mid = fix((low + high)/2); %得到整数值
       
        if array(mid) == element %如果数组对应位置元素相等
            result_index = mid;
            return ;                        %跳出循环返回
        end
        if array(mid) < element  %如果数组对应元素小于,则需要改变下标值
             low = mid + 1;
        else                      %如果数组对应元素大于,则需要改变上标值
             high = mid - 1;
        end
        if low > high              %如果数组对应元素上下标大小对换,默认输出方式
            result_index = NaN;
            return ;
        end
    end
    

    end

    注意:1.分请脚本文件和函数文件,二则不能放在一起运行。
    2.matlab数组下标是从1开始。
    3.3/2不能自动取整,需用fix()函数左取整
    4.拼写错误导致输出变量没有赋值

    展开全文
  • 有序数组二分查找

    千次阅读 2016-07-10 21:20:15
    来看第一个问题:数组二分查找。 数组是我们常见的数据结构,在程序设计中应用广泛。关于数组的操作通常是:查找、插入、删除。二分查找是我们常用的一种查找方式,效率比较高。提到二分查找,最原始的方式是线性...
  • 二维数组二分查找

    千次阅读 2015-10-29 20:26:46
    二维数组二分查找一个二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组一个整数,判断数组中是否含有该整数。 解题思路从...
  • 旋转数组二分查找

    千次阅读 2014-07-09 08:56:15
    1、什么是旋转数组 ...2、旋转数组二分查找之找到给定key 对于给定一个数key,如何从旋转数组中找到key的位置呢?由于旋转数组部分有序,故可以利用二分查找思想来设计算法,从而达到logn的时间复杂度。
  • 有序数组和无序数组二分查找

    千次阅读 2017-04-22 10:33:37
    1. 有序数组二分查找这种情况下,也是最经常的二分查找。 已知一个已经按递增(或递减)排好序的数组,想找到某个数值为k的元素。根据下标idx查找#include #include #include using namespace std; int binary...
  • 本篇文章主要介绍了详解Java数据结构和算法(有序数组二分查找),具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 二分查找,前提是一个有序数组,原理很简单 如图:先找出数组中间 的数,与你需要查找的数进行比较,如果比中间数小(如图)就区左半部分的中间数在与需要查找的数进行比较(需要递归),直到找到为止。相反如果比中间数...
  • 实现有序数组二分查找 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;
  • 数组二分查找

    2019-05-23 19:01:03
    数组二分查找(根据元素) 代码详解 package arrays; /** 数组二分查找 条件:数组元素不能重复且有序 结果:有则返回下标元素 无则返回-1 */ public class ArrayBinarySearch { ...
  • 昨天晚上砍了一道算法题,题目要求使用二分查找数组中某一个值,唯一的不同是该数组是在原始有序的情况下,按照某一个进行了旋转,对于这个数组,有一个角度来思考问题,其关键思想是寻找旋转点。对于旋转数组,...
  • //有序升序数组二分查找 #include<stdio.h> #include<windows.h> //控制台显示 int BinSearch(int arr[],int num, int x) { int left = 0; int right = num - 1; while (left<=right) //条件判定 ...
  • 从初学者的角度来进行了解什么是二分查找。 二分查找就相当于猜数游戏。我们小时候经常玩的猜数游戏中所用的方法一样。在这个游戏里,一个朋友会让你猜他正想的一个1至100之间的数。当你猜了一个数后,他会告诉你三...
  • 题目地址:牛客:有重复数字的有序数组二分查找 题目描述 请实现有重复数字的有序数组二分查找。 输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。 示例1 输入 ...
  • 请实现有重复数字的升序数组二分查找: 给定一个 元素有序的(升序)整型数组 nums 和一个目标值 target ,写 一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1 示例1 输入 [1,2,4,4,5],4 ...
  • java数组二分查找

    2015-11-02 16:56:58
    Java数组二分查找代码,将给定数组排序,然后接收键盘键入的整形数字,并查找该数字。
  • 二分查找 请实现有重复数字的有序数组二分查找。 输出在数组中第一个大于等于查找值的位置,如果数组中不存在这样的数,则输出数组长度加一。 输入 5,4,[1,2,4,4,5] 输出 3(从1开始的哦。不是index) 思路: 1....
  • 旋转有序数组二分查找

    千次阅读 2018-05-23 16:03:55
    比如,数组为: int[] arr = {15, 16, ...每次根据left和right求出mid后,mid的左边为[left, mid], mid的右边为[mid + 1, right],这两部分中至少有一个是有序的。 arr[mid]和key比较 (1). arr[mid] == key,返...
  • 数组部分——二分查找.pdf

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 269,658
精华内容 107,863
关键字:

对一个数组进行二分查找