二分法查找 订阅
算法:二分法查找适用于数据量较大时,但是数据需要先排好顺序。主要思想是:(设查找的数组区间为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。
收起全文
精华内容
下载资源
问答
  • 二分法查找

    2018-05-03 16:00:24
    查询数组中,某一个元素所在的位置
  • 主要介绍了python二分法查找算法实现方法,结合实例形式分析了Python使用递归与非递归算法实现二分查找的相关操作技巧,需要的朋友可以参考下
  • 主要为大家详细介绍了java实现二分法查找出数组重复数字,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
  • 二分法查找MATLAB程序

    2018-03-27 23:18:53
    使用二分法查找的MATLAB程序编写,方便刚接触MATLAB的同学分享学习。
  • 该资源用C语言写的,通俗易懂,用了很多基础的语法,缺点是没有把他编写成调用的函数
  • 二分法查找 *进行二分法查找的前提是数组已有序 *查找范围的上下界
  • C#二分法快速查找查找连续数字,C#二分法快速查找查找连续数字,C#二分法快速查找查找连续数字,C#二分法快速查找查找连续数字,
  • Java基础–基本算法 JAVA主要作为一个后端语言,对逻辑和基本算法的要求是明显高于前端程序员的(个人认为),所以大家平常逻辑性不太好的就需要多多复习和学习来提高自己的水平。 1.冒泡排序(优化排序) ...
  • 写出二分法查找算法函数实现。
  • c++二分法查找

    2021-10-25 08:28:08
    2)同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。 区间的定义: 区间的定义不同代码就不同。 1)定义target在[left, right]区间 while (left <= right) 要...

    二分法:

    二分法应用条件:1)数组为有序数组。2)同时题目还强调数组中无重复元素,因为一旦有重复元素,使用二分查找法返回的元素下标可能不是唯一的。

    区间的定义:

    区间的定义不同代码就不同。
    1)定义target在[left, right]区间
    while (left <= right) 要使用 <= ,因为left == right是有意义的,所以使用 <=。if (nums[middle] > target) right 要赋值为 middle - 1,因为当前这个nums[middle]一定不是target,那么接下来要查找的左区间结束下标位置就是 middle - 1。
    以leecode704为例:

    // 定义target在[left, right]区间
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left = 0;
            int right = nums.size() - 1; // 定义target在左闭右闭的区间里,[left, right]
            while (left <= right) { // 当left==right,区间[left, right]依然有效,所以用 <=
                int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
                if (nums[middle] > target) {
                    right = middle - 1; // target 在左区间,所以[left, middle - 1]
                } else if (nums[middle] < target) {
                    left = middle + 1; // target 在右区间,所以[middle + 1, right]
                } else { // nums[middle] == target
                    return middle; // 数组中找到目标值,直接返回下标
                }
            }
            // 未找到目标值
            return -1;
        }
    };
    
    

    2)如果说定义 target 是在一个在左闭右开的区间里[left, right) :

    // 定义target在[left, right)区间
    // 版本二
    class Solution {
    public:
        int search(vector<int>& nums, int target) {
            int left = 0;
            int right = nums.size(); // 定义target在左闭右开的区间里,即:[left, right)
            while (left < right) { // 因为left == right的时候,在[left, right)是无效的空间,所以使用 <
                int middle = left + ((right - left) >> 1);
                if (nums[middle] > target) {
                    right = middle; // target 在左区间,在[left, middle)中
                } else if (nums[middle] < target) {
                    left = middle + 1; // target 在右区间,在[middle + 1, right)中
                } else { // nums[middle] == target
                    return middle; // 数组中找到目标值,直接返回下标
                }
            }
            // 未找到目标值
            return -1;
        }
    };
    
    

    参考:
    代码随想录:https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%BB%E7%BB%93

    展开全文
  • C++版二分法查找算法

    2012-10-17 15:20:04
    class binary_search { public: int * arr; int nElems; public : binary_search(); binary_search(int max); virtual ~binary_search(); int find(int searchKey); void insert(int value);...
  • 整数二分法查找

    2021-07-21 18:36:56
    二分法查找的前提是序列“有序”。 二分法查找可以确定某种性质在序列中的边界。 当确定该性质的左边界时 ([l,r][l,r][l,r]被分为[l,mid][l,mid][l,mid]和[mid+1,r][mid+1,r][mid+1,r]) while (l < r) { int mid...

    二分法查找的前提是序列“有序”。

    二分法查找可以确定某种性质在序列中的边界。

    当确定该性质的左边界时 ( [ l , r ] [l,r] [l,r]被分为 [ l , m i d ] [l,mid] [l,mid] [ m i d + 1 , r ] [mid+1,r] [mid+1,r])

    while (l < r)
    {
    	int mid = l + r >> 1;//下取整
    	if (check(mid)) r = mid;
    	else l = mid + 1;
    }
    

    当确定该性质的右边界时 ( [ l , r ] [l,r] [l,r]被分为 [ l , m i d − 1 ] [l,mid-1] [l,mid1] [ m i d , r ] [mid,r] [mid,r])

    while (l < r)
    {
    	int mid = l + r + 1 >> 1; //上取整
    	if (check(mid)) l = mid;
    	else r = mid - 1;
    }
    

    关于上下 mid 取整的问题:

    • 当确定该性质的左边界时
      假设 l l l r r r相邻,即 l = r − 1 l = r - 1 l=r1
      若mid向下取整
      则l = mid (此时mid == l)
      会导致死循环
    • 同理,当确定该性质的右边界时
      mid应该向下取整,这样不会出现 r = r 的死循环情况。
    展开全文

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 45,405
精华内容 18,162
关键字:

二分法查找