二分法查找 订阅
算法:二分法查找适用于数据量较大时,但是数据需要先排好顺序。主要思想是:(设查找的数组区间为array[low, high])(1)确定该区间的中间位置K(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下:a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]b.array[k] 展开全文
算法:二分法查找适用于数据量较大时,但是数据需要先排好顺序。主要思想是:(设查找的数组区间为array[low, high])(1)确定该区间的中间位置K(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下:a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]b.array[k]
信息
外文名
Binary Search
要    求
查找算法
中文名
二分法查找
主要思想
数组中元素是有顺序的
二分法查找算法
[一维数组,折半查找]假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.1.开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为a[mid]>x,故应在前半段中查找。2.令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>a[mid],故确定应在后半段中查找。3.令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。例:在有序的有N个元素的数组中查找用户输进去的数据x。算法如下:1.确定查找范围front=0,end=N-1,计算中项mid=(front+end)/2。2.若a[mid]=x或front>=end,则结束查找;否则,向下继续。3.若a[mid]x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。
收起全文
精华内容
下载资源
问答
  • 二分法查找
    2021-12-25 09:28:06

    二分法查找过程:

    1. 找到中间的关键字
    2. 比较查找的关键字与中间关键字的大小关系
    3. 如果相等,那么就算是已找到
    4. 如果查找的关键字小于中间的关键字则在前半部分进行同样的存储
    5. 如果查找的关键字大于中间的关键字则在后半部分进行同样的存储

    二分法查找要求:

    1. 顺序存储
    2. 元素有序

    剑指offer11. 旋转数组的最小数字
    在这里插入图片描述

    class Solution {
        public int minArray(int[] numbers) {
            int left = 0;
            int right = numbers.length - 1;
            if(right == 0){
                return numbers[0];
            }
            while(left < right){
                int mid = left + (right - left) / 2;//防止出现越界问题
                if(numbers[mid] > numbers[right]){//说明旋转点在mid右边
                    left = mid + 1;
                }else if(numbers[mid] < numbers[right]){//说明旋转点在mid左边
                    right = mid;
                }else if(numbers[mid] == numbers[right]){
                    right--;//从最右边-1遍历
                }
            }
            return numbers[left];
        }    
    }
    

    Tips:

    1. 为什么上述代码中是int mid = left + (right - left) / 2;而不是二分法中常见的int mid = (left + right) / 2;
      如果是int mid = (left + right) / 2;的话会在left和right两者较大时发生整型越界

    2. 为什么上述代码中是right = mid;而不是二分法中常见的right = mid - 1;
      如果是right = mid - 1;的话可能会漏掉mid这个值,有可能mid就是旋转点,即题目中所要求返回的值

    3. 此题还有一种解法就是暴力解法,即从下标为0的元素开始遍历,每次进行比较,如果当前元素比相邻的下一个元素大,则对应的下一个元素为最小元素,如果查到最后一个元素没有出现上述元素,则下标为0的元素为最小元素

    更多相关内容
  • 二分法查找

    2018-05-03 16:00:24
    查询数组中,某一个元素所在的位置
  • 主要为大家详细介绍了java实现二分法查找出数组重复数字,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 主要介绍了浅谈二分法查找和原始算法查找的效率对比,具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧
  • 二分法查找 *进行二分法查找的前提是数组已有序 *查找范围的上下界
  • 本篇文章主要介绍了JavaScript用二分法查找数据的实例代码,小编觉得挺不错的,现在分享给大家,也给大家做个参考。一起跟随小编过来看看吧
  • 数组 数组的定义 数组是相同类型数据的有序集合,数组描述的是相同类型的若干个数据,按照一定的先后次序排列组合而成。其中,每一个数据称作一个元素,每个元素可以通过一个索引(下标)来访问它们。...
  • Java基础–基本算法 JAVA主要作为一个后端语言,对逻辑和基本算法的要求是明显高于前端程序员的(个人认为),所以大家平常逻辑性不太好的就需要多多复习和学习来提高自己的水平。 1.冒泡排序(优化排序) ...
  • 写出二分法查找算法函数实现。
  • 此程序可实现二分查找算法,采用的是C编程。
  • 二分法查找算法

    2022-02-25 15:55:34
    二分法查找适用于数据量较大时,但是数据需要先排好顺序。主要思想是:(设查找的数组区间为array[low, high]) (1)确定该区间的中间位置K(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定...


    一、二分法是什么?

    二分法查找适用于数据量较大时,但是数据需要先排好顺序。主要思想是:(设查找的数组区间为array[low, high])
    (1)确定该区间的中间位置K(2)将查找的值T与array[k]比较。若相等,查找成功返回此位置;否则确定新的查找区域,继续二分查找。区域确定如下:a.array[k]>T 由数组的有序性可知array[k,k+1,……,high]>T;故新的区间为array[low,……,K-1]b.array[k]<T 类似上面查找区间为array[k+1,……,high]。每一次查找与中间值比较,可以确定是否查找成功,不成功当前查找区间将缩小一半,递归查找即可。时间复杂度为:O(log2n)。

    二、使用步骤

    [一维数组,折半查找]
    假如有一组数为3,12,24,36,55,68,75,88要查给定的值24.可设三个变量front,mid,end分别指向数据的上界,中间和下界,mid=(front+end)/2.
    1.开始令front=0(指向3),end=7(指向88),则mid=3(指向36)。因为a[mid]>x,故应在前半段中查找。
    2.令新的end=mid-1=2,而front=0不变,则新的mid=1。此时x>a[mid],故确定应在后半段中查找。
    3.令新的front=mid+1=2,而end=2不变,则新的mid=2,此时a[mid]=x,查找成功。
    如果要查找的数不是数列中的数,例如x=25,当第三次判断时,x>a[mid],按以上规律,令front=mid+1,即front=3,出现front>end的情况,表示查找不成功。
    例:在有序的有N个元素的数组中查找用户输进去的数据x。
    算法如下:
    1.确定查找范围front=0,end=N-1,计算中项mid=(front+end)/2。
    2.若a[mid]=x或front>=end,则结束查找;否则,向下继续。
    3.若a[mid]<x,说明待查找的元素值只可能在比中项元素大的范围内,则把mid+1的值赋给front,并重新计算mid,转去执行步骤2;若a[mid]>x,说明待查找的元素值只可能在比中项元素小的范围内,则把mid-1的值赋给end,并重新计算mid,转去执行步骤2。

    三、代码实现

    import java.util.Arrays;
    
    public class Test2 {
        public static void main(String[] args) {
            //1、定义数组
            int[] arr = {10, 15, 1, 9, 16, 36, 35, 39, 95, 56};
            Arrays.sort(arr);//给数组排序
            System.out.println(Arrays.toString(arr));
    
            System.out.println(binarySearch(arr, 56));
        }
    
        public static int binarySearch(int[] arr, int data) {
            //1、定义左边和右边位置
            int left = 0;
            int right = arr.length - 1;
    
            //2、开始循环、折半查找
            while (left <= right) {
                //取中间索引
                int middleIndex = (left + right) / 2;
                //3、判断当前中间位置的元素和要找的元素的大小情况
                if (data > arr[middleIndex]) {
                    //往右边找,左位置更新为=中间索引+1
                    left = middleIndex + 1;
                } else if (data < arr[middleIndex]) {
                    //往左边找,右边位置=中间索引-1
                    right = middleIndex - 1;
                } else {
                    return middleIndex;
                }
            }return -1;//查找失败
        }
        
    }
    

    效果

    在这里插入图片描述

    总结

    1、数组的二分查找的实现步骤是什么样的? 定义变量记录左边和右边位置。

    使用while循环控制查询(条件是左边位置<=右边位置)
    循环内部获取中间元素索引
    判断当前要找的元素如果大于中间元素,左边位置=中间索引+1
    判断当前要找的元素如果小于中间元素,右边位置=中间索引-1
    判断当前要找的元素如果等于中间元素,返回当前中间元素索引。

    展开全文
  • ——二分法查找 目录 课程导入 1 清楚并牢记二分法的实现条件 2 理解二分法的实现思路 3 读懂二分法的实现代码 数组的查找——二分法查找 也称拆半查找法,是一种高效的查找方法,前提条件是数组元素必须已经按升序...
  • C语言编程学习,使用二分法查找最大/最小数据

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 54,022
精华内容 21,608
关键字:

二分法查找