二分查找 订阅
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 [1] 展开全文
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 [1]
信息
外文名
Binary Search
提出时间
1946
别    称
折半查找
提出者
John Mauchly
应用学科
计算机
中文名
二分查找
适用领域范围
编程语言
缺    点
待查表为有序表
优    点
查找速度快
时间复杂度
O(log2n) [1]
二分查找查找过程
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。
收起全文
精华内容
下载资源
问答
  • 二分查找
    千次阅读
    2021-02-02 15:41:50

    一、算法解释

    二分查找也常被称为二分法或者折半查找,每次查找时通过将待查找区间分成两部分并只取一部分继续查找,将查找的复杂度大大减少。对于一个长度为 O(n) 的数组,二分查找的时间复杂度为 O(log n)

    • 基本思想:在一个区间范围里,看处在中间位置的元素的值与目标值的大小关系,从而决定目标值落在哪一个半区间里

    • 一般代码结构

       public int binarySearch(int[] nums, int target) {
          //初始化搜索区间[left,right]
          int left = 0, right = nums.length - 1;
          int ans = -1;
          while (left <= right) {
              int mid = (left + right) / 2;
              //mid的值符合条件
              if(nums[mid] == target){ 
              	ans=mid;
                  //...可能会有其他操作,若没有直接return
              }
              //缩小搜索区间
              if (nums[mid] > target) {//锁定左半区间
                  right = mid - 1;
              } else {//锁定右半区间
                  left = mid + 1;
              }
          }
          return ans;
      }
      
    • 二分查找时区间的左右端取开区间还是闭区间在绝大多数时候都可以

    有些初学者会容易搞不清楚如何定义区间开闭性。这里我提供两个小诀窍:

    • 第一是尝试熟练使用一种写法,比如左闭右开(满足 C++、Python 等语言的习惯)或左闭右闭(便于处理边界条件),尽量只保持这一种写法;

    • 第二是在刷题时思考如果最后区间只剩下一个数或者两个数,自己的写法是否会陷入死循环,如果某种写法无法跳出死循环,则考虑尝试另一种写法。

      死循环举例:

      int start,end,mid;
      mid = (end-start)>>1+start;
      while(end > start ){
          if(array[mid] == x)
              return mid;
          if(array[mid] < x)
          	start = mid;
      	else
          	end = mid;
      }
      

      只有两个元素时,有mid=start,如果这次依然需要移动start,则会有start=mid,进入死循环

    • 二分查找也可以看作双指针的一种特殊情况,但我们一般会将二者区分。双指针类型的题,指针通常是一步一步移动的,而在二分查找里,指针每次移动半个区间长度。

    二、求开方

    ⭐️nums[mid] == target可以换成其他条件(这里换成了平方值)、乘法溢出问题

    69. x 的平方根

    实现 int sqrt(int x) 函数。

    计算并返回 x 的平方根,其中 x 是非负整数。

    由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。

    示例 1:

    输入: 4
    输出: 2
    

    示例 2:

    输入: 8
    输出: 2
    说明: 8 的平方根是 2.82842..., 
         由于返回类型是整数,小数部分将被舍去。
    
    • 边界情况
      • ”x非负“:x=0时
      • [0,x]之间上的数值a可能会出现a*a>MAX_INT,即乘方时溢出
    思路一:二分查找
    • 在[0, x] 区间找到a,满足”[sqrt(x)]==a"。因此可以使用二分查找的方法

    • 逆向思路防止乘方时溢出:判断mid*mid与x ===>判断x/mid与mid

    • 代码

      class Solution {
          public int mySqrt(int x) {
              if(x < 0)
                  return -1;
              if(x <=1)
                  return x;//"非负">,=0
              //二分查找
              int start=1,end=x;
              while(end > start){
                  int mid=(end-start)/2+start;//mid>=start
                  
                  int res = x/mid;//注意这里会向下取整
                  if(res == mid)//[sqrt(X)] == mid
                      return mid;
                  if(res > mid){//mid*mid < X
                      start=mid+1;
                  }
                  else{
                      end=mid;
                  }
                  //end,start一个=mid一个=mid+1的原因是:end-start=1时mid=start
              }
              //end=start
              return x/end;
          }
      }
      
    思路二:牛顿迭代法

    牛顿法的作用是使用迭代的方法来求解函数方程的根。简单地说,牛顿法就是不断求取切线的过程。

    迭代公式: x n + 1 = x n − f ( x n ) / f ′ ( x n ) x_{n+1} = x_n − f (x_n)/ f′(x_n) xn+1=xnf(xn)/f(xn)

    img

    对于形如f(x)=0的方程,首先任意估算一个解x0,再把该估计值代入原方程中。由于一般不会正好选择到正确的解,所以有f(x)=a。这时计算函数在x0处的斜率,和这条斜率与x轴的交点x1

    f(x)=0中精确解的意义是,当取得解的时候,函数值为零(即f(x)的精确解是函数的零点)。因此,x1比x0更加接近精确的解。只要不断以此方法更新x,就可以取得无限接近的精确的解

    是已知的实现求方根最快的方法之一,只需要迭代几次后就能得到相当精确的结果

    求a的方根的方程为 f ( x ) = x 2 − a = 0 f(x)=x^2-a=0 f(x)=x2a=0,迭代公式为$ x_{n+1} = (x_n + a/x_n)/2, $

    int mySqrt(int a) {
        int x = a;
        while (x > a/x) {
            x = (x + a / x) / 2;
        }
        return x;
    }
    

    三、查找区间/边界

    ⭐️target在数组中可能存在多个,mid大于等于/小于等于

    34. 在排序数组中查找元素的第一个和最后一个位置

    给定一个按照升序排列的整数数组 nums,和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

    如果数组中不存在目标值 target,返回 [-1, -1]。

    进阶:你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗?

    示例 1:

    输入:nums = [5,7,7,8,8,10], target = 8
    输出:[3,4]
    

    示例 2:

    输入:nums = [5,7,7,8,8,10], target = 6
    输出:[-1,-1]
    

    示例 3:

    输入:nums = [], target = 0
    输出:[-1,-1]
    

    提示:

    • 0 <= nums.length <= 1 0 5 10^5 105
    • − 1 0 9 -10^9 109 <= nums[i] <= 1 0 9 10^9 109
    • nums 是一个非递减数组
    • − 1 0 9 -10^9 109 <=target <= 1 0 9 10^9 109
    原始思路:二分查找+双向遍历
    • 测试用例

      [],1			=> [-1,-1]
      [0],1			=> [-1,-1]   //1. 没有(二分查找target返回-1)的情况
      [1],1			=> [0,0]
      [1,1,2,3],1		=> [0,1]	 //2. 从0号开始的情况(只有一个/多个)
      [1,2,2,2],2		=> [1,3]	 //3. 到结尾的情况
      [1,2,2,3],2		=> [1,2]	 //4. 从中间开始的情况/一般情况
      
    • 策略:二分查找+双向遍历,时间复杂度为T(n)

      还不如干脆只遍历(记录第一个等于target的位置,和之后第一个大于target的位置)

      没有充分理解二分查找的作用/应用

      先用二分查找获得target在数组中的一个下标index

      • 若下标为-1表示没有该数值返回[-1,-1](测试用例1)
      • 若下标不是-1,以该下标index为中心,使用左右双指针遍历数组找到target在数组中的起始位置(其中测试用例中2和3是遍历时需要考虑的特殊情况)
    • 代码

      class Solution {
          public int[] searchRange(int[] nums, int target) {
              //单元测试
              // System.out.println("index="+binarySearch(nums,target));
              // return new int[]{-1,-1};
              int index = binarySearch(nums,target);
              if(index == -1)
                  return new int[]{-1,-1};
              int left=index,right=index;
              //双指针遍历
              while( left >= 0 && nums[left]==target)
                  left--;
              while(right <= nums.length-1 && nums[right]==target)
                  right++;
              left= nums[0] == target? 0 :left+1;
              right = nums[nums.length-1] ==target?nums.length-1:right-1;
              return new int[]{left,right};
          }
          public int binarySearch(int[] nums,int target){
              if(nums.length==0)
                  return -1;
              int start=0,end=nums.length-1,mid;
              while(start <= end){
                  mid=(start+end)/2;
                  if(nums[mid] == target)
                      return mid;
                  if(nums[mid] < target)
                      start = mid+1;
                  else
                      end = mid-1;
              }
              return -1;
          }
      }
      
    • 其他:

      • 工具函数binarySearch()

        • 注意命名简洁性
        • 编写完成后首先进行单元测试
      • 双指针遍历时

        //++/--的条件是:依然=target且下标合法
        while(left >= 0 && nums[left]==target)
            left--;
        while(right <= nums.length-1 && nums[right]==target)
            right++;
        

        left/right作为下标的限制要放在前面(利用逻辑运算的短路特性,避免出现nums[-1]==target的情况)

    思路二:二分查找

    时间复杂度为 l o g n log^n logn

    nums[mid] == target时,还要继续查找下去(继续使用二分查找),可以找到target的左边界/右边界。详细步骤:

    若此时有nums[mid] == target,先令res=mid

    • 找左边界(index的min):在mid左侧的子区间继续寻找target,用更小的index更新res
    • 找右边界(index的max):在mid右侧的子区间继续寻找target,用更大的index更新res
    //leftOrRight为true找左边界 false找右边界
    public int binarySearch(int[] nums, int target, boolean leftOrRight) {
        int res = -1;
        int left = 0, right = nums.length - 1, mid;
        while(left <= right) {
            mid = (right + left) / 2;
            if(target < nums[mid])
                right = mid - 1;
            else if(target > nums[mid])
                left = mid + 1;
            else {
                res = mid;
                //处理target == nums[mid]
                if(leftOrRight)//在mid左侧的子区间继续寻找target
                    right = mid - 1;
                else//在mid右侧的子区间继续寻找target
                    left = mid + 1;
            }
        }
        return res;//index的min/max
    }
    

    综合一下:

    • 求左边界时用nums[mid] >= target(左移搜索区间)

    • 求右边界时用nums[mid] <= target(右移搜索区间)

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

    调用两次该工具函数,求出target区间

    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[] {-1, -1};
        res[0] = binarySearch(nums, target, true);
        res[1] = binarySearch(nums, target, false);
        return res;
    }
    

    四、旋转数组查找数字

    33. 搜索旋转排序数组

    升序排列整数数组 nums 在预先未知的某个点上进行了旋转(例如, [0,1,2,4,5,6,7] 经旋转后可能变为 [4,5,6,7,0,1,2] )。

    请你在数组中搜索 target ,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 。

    示例 1:

    输入:nums = [4,5,6,7,0,1,2], target = 0
    输出:4
    

    示例 2:

    输入:nums = [4,5,6,7,0,1,2], target = 3
    输出:-1
    

    示例 3:

    输入:nums = [1], target = 0
    输出:-1
    

    提示:

    • 1 <= nums.length <= 5000
    • -10^4 <= nums[i] <= 10^4
    • nums 中的每个值都独一无二
    • nums 肯定会在某个点上旋转
    • -10^4 <= target <= 10^4
    • 问题分析:

      • 原始的nums数组严格单调递增
      • 找到旋转位置,对两侧分别进行二分查找
        • 特殊旋转位置:0和length-1
      • 时间复杂度T(n),同遍历搜索
    • 代码:

      class Solution {
          public int search(int[] nums, int target) {
              if(nums.length == 0)
                  return -1;
              int pos=0;
              for(pos=0; pos < nums.length-1; pos++){
                  if(nums[pos] > nums[pos+1])
                      break;
              }
              int index = binarySearch(nums,target,0,pos);
              // System.out.println("index1="+index);
              if(index != -1)
                  return index;
              index = binarySearch(nums,target,pos+1,nums.length-1);//不能是pos,必须保证有序
              // System.out.println("index2="+index);
              return index;
      
          }
          public int binarySearch(int[] nums, int target, int left, int right){
              int mid;
              // System.out.println("["+left+", "+right+"]");
              if(left < 0 || right > nums.length-1 || nums.length==0)
                  return -1;
              while(left <= right){
                  mid = (left + right) / 2;
                  if(nums[mid] == target)
                      return mid;
                  if(nums[mid] < target)
                      left = mid + 1;
                  else
                      right = mid - 1;
              }
              return -1;
          }
      }
      
    • ⭐️二分搜索思想的核心是可以把问题规模每次减小一半(每次确定target必须在哪半个区间),利用该思想:

      • 将原数组切分成两半,一定有一半是有序的,另一半可能是有序/部分有序的。

        • mid大于right:右边部分有序说明左边一定有序
        • mid小于left:左边部分有序说明右边一定有序
      • 通过有序的一半区间的取值范围可以判断出target会在哪个半区间,进而将问题规模缩小一半

      • 代码

        class Solution {
            public int search(int[] nums, int target) {
                int start = 0, end = nums.length-1;
                int mid;
                while(start <= end){
                    mid = (start + end)/2;
                    if(nums[mid] == target)
                        return mid;
                    //缩小搜索区间
                    if(nums[mid] < nums[start]){//右半区间有序
                        if(target > nums[mid] && target <= nums[end])//target在右半区间
                            start = mid + 1;
                        else
                            end = mid - 1;
                    }
                    else{//左半区间有序
                        if(target >= nums[start] && target<nums[mid])//target在左半区间
                            end = mid - 1;
                        else
                            start = mid + 1;
                    }
                
                }
                return -1;
            }
        }
        

    81. 搜索旋转排序数组 II

    假设按照升序排序的数组在预先未知的某个点上进行了旋转。

    ( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

    编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,否则返回 false。

    示例 1:

    输入: nums = [2,5,6,0,0,1,2], target = 0
    输出: true
    

    示例 2:

    输入: nums = [2,5,6,0,0,1,2], target = 3
    输出: false
    

    进阶:

    • 这是 搜索旋转排序数组 的延伸题目,本题中的 nums 可能包含重复元素。
    • 这会影响到程序的时间复杂度吗?会有怎样的影响,为什么?
    • 因为数组存在重复数字,如果中点和左端的数字相同,我们并不能确定是左区间全部 相同,还是右区间完全相同。在这种情况下,我们可以简单地将左端点右移一位,然后继续进行二分查找。

    • 代码

      class Solution {
          public boolean search(int[] nums, int target) {
              int start = 0, end = nums.length-1;
              int mid;
              while(start <= end){
                  mid = (start + end)/2;
                  if(nums[mid] == target)
                      return true;
                  //缩小搜索区间
                  //无法判断哪个区间有序
                  if(nums[mid] == nums[start] && start<=nums.length-1)
                      start++;
                  else if(nums[mid] < nums[start]){//右半区间有序
                      if(target > nums[mid] && target <= nums[end])//target一定在右半区间
                          start = mid + 1;
                      else
                          end = mid - 1;
                  }
                  else{//左半区间有序
                      if(target >= nums[start] && target < nums[mid])//target在左半区间
                          end = mid - 1;
                      else
                          start = mid + 1;
                  }
              }
              return false;
          }
      }
      
    更多相关内容
  • 查找算法之二分查找算法

    千次阅读 2022-05-18 16:02:02
    图文并茂带你入门二分查找算法 原理 二分查找(Binary Search)算法,也叫折半查找算法。二分查找的思想非常简单,有点类似分治的思想。二分查找针对的是一个有序的数据集合,每次都通过跟区间的中间元素对比,将待...

    图文并茂带你入门二分查找算法

    原理

    二分查找(Binary Search)算法,也叫折半查找算法。二分查找的思想非常简单,有点类似分治的思想。二分查找针对的是一个有序的数据集合,每次都通过跟区间的中间元素对比,将待查找的区间缩小为之前的一半,直到找到要查找的元素,或者区间被缩小为 0。

    为了方便理解,我们以数组1, 2, 4, 5, 6, 7, 9, 12, 15, 19, 23, 26, 29, 34, 39,在数组中查找26为例,制作了一张查找过程图,其中low标示左下标,high标示右下标,mid标示中间值下标

    img

    二分查找的过程就像上图一样,如果中间值大于查找值,则往数组的左边继续查找,如果小于查找值这往右边继续查找。二分查找的思想虽然非常简单,但是查找速度非常长,二分查找的时间复杂度为O(logn)。虽然二分查找的时间复杂度为O(logn)但是比很多O(1)的速度都要快,因为O(1)可能标示一个非常大的数值,比例O(1000)。我们来看一张二分查找与遍历查找的效率对比图。

    img

    ❝ 图片来源网络

    从图中可以看出二分查找用了三步就找到了查找值,而遍历则用了11步才找到查找值,二分查找的效率非常高。但是二分查找的局限性非常大。那二分查找有哪些局限性呢?

    局限性

    二分查找依赖数组结构

    二分查找需要利用下标随机访问元素,如果我们想使用链表等其他数据结构则无法实现二分查找。

    二分查找针对的是有序数据

    二分查找需要的数据必须是有序的。如果数据没有序,我们需要先排序,排序的时间复杂度最低是 O(nlogn)。所以,如果我们针对的是一组静态的数据,没有频繁地插入、删除,我们可以进行一次排序,多次二分查找。这样排序的成本可被均摊,二分查找的边际成本就会比较低。

    但是,如果我们的数据集合有频繁的插入和删除操作,要想用二分查找,要么每次插入、删除操作之后保证数据仍然有序,要么在每次二分查找之前都先进行排序。针对这种动态数据集合,无论哪种方法,维护有序的成本都是很高的。

    所以,二分查找只能用在插入、删除操作不频繁,一次排序多次查找的场景中。针对动态变化的数据集合,二分查找将不再适用

    数据量太小不适合二分查找

    如果要处理的数据量很小,完全没有必要用二分查找,顺序遍历就足够了。比如我们在一个大小为 10 的数组中查找一个元素,不管用二分查找还是顺序遍历,查找速度都差不多,只有数据量比较大的时候,二分查找的优势才会比较明显。

    数据量太大不适合二分查找

    二分查找底层依赖的是数组,数组需要的是一段连续的存储空间,所以我们的数据比较大时,比如1GB,这时候可能不太适合使用二分查找,因为我们的内存都是离散的,可能电脑没有这么多的内存。

    代码实现

    二分查找可以使用循环或者递归来实现,我们来看看两种实现方式的代码。

    循环

    /**
         * 循环版二分查找
         *
         * @param nums  数组
         * @param n     数组长度
         * @param value 要查找的值
         * @return
         */
        private static int bserach(int[] nums, int n, int value) {
            int low = 0;
            int high = n - 1;
            while (low <= high) {
                // 找出中间下标 
                int mid = low + ((high - low) >> 1);
                if (nums[mid] > value) {
                    high = mid - 1;
                } else if (nums[mid] < value) {
                    low = mid + 1;
                } else {
                    return mid;
                }
            }
    
            return -1;
        }
    

    递归

    /**
         * 递归算法实现二分查找
         *
         * @param nums  数组
         * @param low   左下标
         * @param high  右下标
         * @param value 要查找的值
         * @return
         */
        private static int recursiveBserach(int[] nums, int low, int high, int value) {
    
            if (low > high) return -1;
    
            // 找出中间下标
            int mid = low + ((high - low) >> 1);
    
            if (nums[mid] == value) {
                return mid;
    
            } else if (nums[mid] > value) {
                return recursiveBserach(nums, low, mid - 1, value);
            } else {
                return recursiveBserach(nums, mid + 1, high, value);
            }
        }
    

    二分查找的代码实现起来比较简单,需要说明的地方是中间值的计算,中间值得计算有两种方式,方式一:int mid = (low +high)>>1,方式二:int mid = low + ((high - low) >> 1)。方式一存在溢出的风险,当lowhigh比较大时,有可能会导致mid的值错误,从而使程序出错。方式二则可以保证生成的mid一定大于low,小于high

    上面的二分查找比较简单,我们来看看变形的二分查找。

    查找第一个等于给定值的元素

    比如我们给定数组1,2,3,4,4,4,5,6,7,7,8,9,我们需要查找第一个等于4的元素。

        /**
         * 查找第一个等于给定值的元素
         *
         * @param nums
         * @param length
         * @param value
         * @return
         */
        private static int bsearchFirstValue(int[] nums, int length, int value) {
            int low = 0;
            int high = length - 1;
            while (low <= high) {
                int mid = low + ((high - low) >> 1);
                if (nums[mid] > value) {
                    high = mid - 1;
                } else if (nums[mid] < value) {
                    low = mid + 1;
                } else {
                    // 判断当前是第一个元素或者前一个元素不等于要查找的值,则返回下标,如果前一个元素也等于要查找的值,则继续往前查找。
                    if ((mid == 0) || (nums[mid - 1] != value)) return mid;
                    else high = mid - 1;
                }
            }
            return -1;
        }
    

    其他的都差不多,主要的区别是在nums[mid]==value时候,因为我们要查找的是第一个等于给定值的元素,所以我们需要判断mid的前一个元素等不等于给定值,如果前一个元素也等于给定值,则需要继续往左边查找。

    查找第一个大于给定值的元素

    比如我们给定数组1,2,3,4,4,4,5,6,7,7,8,9,15,26,34,45,我们随便输入一个值,这个值可以是数组里面的值,也不可不在数组里面,查找出第一个比给定值大的元素。

    /**
         * 查找第一个大于给定值的元素
         *
         * @param nums   数组
         * @param length 数组的长度
         * @param value  给定的值
         * @return
         */
        private static int bserachFirstOverVlaue(int[] nums, int length, int value) {
            int low = 0;
            int high = length - 1;
            while (low <= high) {
                int mid = low + ((high - low) >> 1);
                if (nums[mid] > value) {
                    // 判断当前是第一个元素或者前一个元素小于等于给定值,则返回下标,如果前一个元素大于给定的值,则继续往前查找。
                    if ((mid == 0) || nums[mid - 1] <= value) return mid;
                    else high = mid - 1;
                } else {
                    low = mid + 1;
                }
            }
            return -1;
        }
    

    我们需要判断当nums[mid] > value时,nums[mid-1]是否小于或者等于给定值,如果是则mid就是第一个大于给定值的元素,如果不是这继续往左边查找。

         low = mid + 1;
            }
        }
        return -1;
    }
    
    
    我们需要判断当`nums[mid] > value`时,`nums[mid-1]`是否小于或者等于给定值,如果是则`mid`就是第一个大于给定值的元素,如果不是这继续往左边查找。
    
    以上就是关于二分查找的相关知识,二分查找虽然性能比较优秀,但应用场景也比较有限,底层必须依赖数组,并且还要求数据是有序的。所以我们在选用算法时需要从多方面考虑。
    
    展开全文
  • 很多人对二分很困惑,可能二分的边界很难掌握,也许是判断条件难写... 很幸运,你找到了这篇文章,仔细看下去,这篇文章将带你**学透二分**!!!

    很多人对二分感到很苦恼,很困惑,可能是因为二分的边界很难掌握,也许是判断条件难写…

    然而,很幸运,你找到了这篇文章,仔细看下去,这篇文章将带你学透二分!!!

    二分可以简单分为二分查找二分答案

    可能你听说过二分查找,二分查找和二分答案是不是一回事呢?答案是否定的。二分查找只是单纯的查找就可以了,简单的控制好边界条件。而二分答案也许稍复杂些。

    首先,我们看一下二分的模板:

    模板1:
    	while (l < r)
        {
            int mid = l + r >> 1;	//(l+r)/2
            if (check(mid))  r = mid;    // check()判断mid是否满足性质
            else l = mid + 1;
        }
    
    模板2:
    	while (l < r)
        {
            int mid = l + r + 1 >> 1;	//(l+r+1)/2
            if (check(mid))  l = mid;
            else r = mid - 1;
        }
    

    看到这,以后的你就不会因为边界问题而困惑了!!!

    第一个模板是尽量往左找目标,第二个模板是尽量往右找目标。

    只要是往左找答案,就用第一个模板,mid不用加一,r=mid,l加一;
    只要是往右找答案,就用第二个模板,mid要加一,l=mid,r要减一;

    二分套这两个模板,肯定没错!(只要判断条件写对)亲测有效!!!
    下面的题目更能证明这句话!

    这两个模板一定要牢牢记住哦

    当然,二分可能在实数中进行,那自然少不了浮点二分。

    模板3:(浮点二分)
    	while(r-l>1e-5) //需要一个精度保证
    	{
    		double mid = (l+r)/2;
    		if(check(mid)) l=mid; //或r=mid;
    		else r=mid; //或l=mid;
    	}
    

    浮点二分就相对简单多了,因为浮点除法不会取整,所以mid,l,r,都不用加1或减1.

    我们先来学二分查找:

    二分查找也称折半查找,顾名思义,就是每次查找去掉不符合条件的一半区间,直到找到答案(整数二分)或者和答案十分接近(浮点二分)。

    光说不练假把式,来个例题:

    例题1——查找

    在这里插入图片描述
    分析:这题就是典型的二分查找入门题。

    首先,区间是有单调性的,查找第一次出现的位置,如果查到一个值比目标值大,就把右半边放弃,因为右半边肯定也比目标值大;同样,如果查到值比目标值小,那就放弃左半边。

    本文的所有例题都有分析,题解,并注上详细注释。先自己尝试一下,再看题解哦。

    code:

    #include<iostream>
    using namespace std;
    
    const int N=1000010;
    int a[N],x,q,n;
    
    int main(){
    	cin>>n>>q;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	
    	while(q--)
    	{
    		cin>>x;
    		int l=1,r=n; //左右边界 
    		while(l<r) //因为是找第一次出现的位置,那就是尽量往左来,就用模板1 
    		{
    			int mid=l+r>>1;
    			if(a[mid]>=x) r=mid; //判断条件,如果值大于等于目标值,说明在目标值右边,尽量往左来
    			else l=mid+1;
    		}
    		if(a[l]!=x){ //如果找不到这个值 
    			cout<<-1<<" ";
    			continue;
    		}
    		cout<<l<<" ";
    	}
    	return 0;
    } 
    

    有一个小问题就是,如果找不到这个值(即,集合里没有这个数)怎么办?因为判断条件是大于等于目标值,那返回的就是第一个大于目标值的位置。

    好了,现在的你已经进入了二分世界的大门,此时让我们畅游吧!

    例2——A-B 数对

    在这里插入图片描述

    分析:给出了C,我们要找出A和B。我们可以遍历数组,即让每一个值先变成B,然后二分找对应的A首次出现位置,看是否能找到。

    如果找到A,那就二分找最后出现的位置,继而,求出A的个数,即数对的个数。

    code:

    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=200010;
    long long a[N],n,c,cnt,st;
    
    int main(){
    	cin>>n>>c;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	sort(a+1,a+1+n);	//先排序 
    	
    	for(int i=1;i<n;i++)	//遍历每一个B 
    	{
    		int l=i+1,r=n;	//寻找A第一次出现的位置,使得A-B=C 
    		while(l<r) //因为是第一次出现,尽量往左,模板1
    		{
    			int mid=l+r>>1;
    			if(a[mid]-a[i]>=c) r=mid;	//判断:在目标值的右边,满足,往左来
    			else l=mid+1;
    		}
    		if(a[l]-a[i]==c) st=l; //能找到C就继续 
    		else continue;
    		
    		l=st-1,r=n;	//查找A最后出现的位置 
    		while(l<r) //因为是最后一次出现,尽量往右,模板2
    		{
    			int mid=l+r+1>>1;
    			if(a[mid]<=a[st]) l=mid; //判断:在目标值的左边,满足,往右去
    			else r=mid-1;
    		}
    		cnt+=l-st+1;	//最后出现的位置减首次出现的位置就是区间长度,即A的个数 
    	}
    	cout<<cnt;
    	return 0;
    } 
    

    如果你把上面的两个题完全搞懂了,那很容易就抽象出做题步骤:

    如果题目明确说了 要求最小值(最前面的值)还是求最大值(最后面的值),就能判断是用模板1(求最小),还是用模板2(求最大)。
    之后再根据模板1,或模板2,写出对应的判断条件;

    但是,我们不建议死记模板,更重要的是在理解之后的灵活变通。比如,再看一个题。

    例3——烦恼的高考志愿

    在这里插入图片描述

    分析:这题,就需要稍微理解一下下。

    要求估分和分数线相差最小,那肯定分数线刚超过估分或者估分刚超过分数线。我们就转化为,求第一个大于等于估分的分数线的位置。

    如此,这个位置的分数线或前一位置的分数线就是和估分相差最小的。

    code:

    #include<bits/stdc++.h>
    using namespace std;
    
    const int N=1e5+10;
    long long a[N],x,sum,n,m;
    
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++) cin>>a[i];
    	sort(a+1,a+n+1); //排序勿忘 
    	a[0]=-1e12;a[n+1]=1e12;	 //最后再解释
    	
    	while(m--)
    	{
    		cin>>x;
    		int l=1,r=n+1;	//r设为n+1 
    		while(l<r) //寻找第一个超过估分的学校,那它或它前面的一个学校就是目标学校 
    		{
    			int mid=l+r>>1;
    			if(a[mid]>=x) r=mid;
    			else l=mid+1;
    		}
    		if(a[l]-x<=x-a[l-1]) sum+=a[l]-x;
    		else sum+=x-a[l-1];
    	}
    	
    	cout<<sum;
    	return 0;
    	//a[0]=-1e12: 所有分数先可能都比估分大,那么l就为1,n-1就为0,故设a[0]为无穷小,则第一个值就为解 
    	//a[n+1]=1e12: 所有分数线可能都比估分小,那么l就为n,a[l]-x可能为负,则设a[n+1]为无穷大,
    				//并将r设为n+1,如此,l最大为n+1,则最后一个就为解 
    }
    

    此外,STL中还有两个二分函数:lower_bound 和 upper_bound;具体可以看这个博客;或这个(有很多大佬总结的知识点都很好,有啥不懂的话都可以翻博客)
    有了这两个函数,我们就可以很方便的求出第一个大于(或等于)目标值的位置;于是,上面代码的中间可以这样改:

    while(m--)
    	{
    		cin>>x;
    		int t=lower_bound(a+1,a+n+1,x)-a; //如果分数线都比估分低,那返回的位置是n+1,否则返回第一个大于等于估分的位置。
    		if(a[t]-x<=x-a[t-1]) sum+=a[t]-x;
    		else sum+=x-a[t-1];
    	}
    

    是不是简洁多了?

    最后,我们再来看一个浮点二分:

    例4——银行贷款在这里插入图片描述

    分析:对于月利率,大几率是小数,那么,我们就需要浮点二分。

    月利率的范围可以放大些,比如,0~500,然后从这个范围里查,直到和答案极度相近,终止。 最后的l或r,精确位数之后就是正确✔答案啦!

    code:

    #include<bits/stdc++.h>
    using namespace std;
    
    int sum,t,mon;
    double sumt;
    
    int check(double mid)
    {
    	sumt=sum;
    	for(int i=1;i<=mon;i++){
    		sumt=sumt+sumt*mid-t;
    	}
    	if(sumt > 0) return 1; 				//这里是>0, 感谢评论区小伙伴提醒~
    	return 0;
    } 
    
    int main(){
    	cin>>sum>>t>>mon;
    	
    	double l=0,r=500; //答案范围尽量开大些
    	while(r-l>1e-5)	//精度保证 
    	{
    		double mid=(l+r)/2;
    		if(check(mid)) r=mid;	//如果最后还不完了,说明利率高了 	
    		else l=mid;
    	}
    	printf("%.1f",l*100);
    	return 0;
    } 
    

    至此,相信你已经对二分查找有一个更加清晰的认识了。

    课后再来几个练习题吧:
    整数二分:
    1、 数的范围
    2、 砍树
    实数二分:
    3、 数的三次方根
    4、 一元三次方程求解

    学会了二分查找,来学二分答案!

    首先:

    二分查找与二分答案有何区别?

    二分查找:在一个已知的有序数据集上进行二分地查找
    二分答案:答案有一个区间,在这个区间中二分,直到找到最优答案

    什么是二分答案?

    答案属于一个区间,当这个区间很大时,暴力超时。但重要的是——这个区间是对题目中的某个量有单调性的,此时,我们就会二分答案。每一次二分会做一次判断,看是否对应的那个量达到了需要的大小。
    判断:根据题意写个check函数,如果满足check,就放弃右半区间(或左半区间),如果不满足,就放弃左半区间(或右半区间)。一直往复,直至到最终的答案。

    其实,上面二分查找的例4,寻找的那个区间就是答案区间。

    这不就相当于高中做选择题的时候,完了,不会做,那咋搞,把四个选项代进去看看对不对吧!哪个行得通那个就是答案!!

    只不过我们现在要找的是最大的或者最小的答案

    如何判断一个题是不是用二分答案做的呢?

    1、答案在一个区间内(一般情况下,区间会很大,暴力超时)
    2、直接搜索不好搜,但是容易判断一个答案可行不可行
    3、该区间对题目具有单调性,即:在区间中的值越大或越小,题目中的某个量对应增加或减少。

    此外,可能还会有一个典型的特征求...最大值的最小 、 求...最小值的最大。
    1、求...最大值的最小,我们二分答案(即二分最大值)的时候,判断条件满足后,尽量让答案往前来(即:让r=mid),对应模板1;
    2、同样,求...最小值的最大时,我们二分答案(即二分最小值)的时候,判断条件满足后,尽量让答案往后走(即:让l=mid),对应模板2;

    先看一个经典的二分答案入门:

    例1——木材加工在这里插入图片描述

    分析:看,答案就在区间(1,100000000)里,就等着我们找呢,暴力肯定超时,那可能就用二分。
    满足条件:

    1,答案在一个区间里。
    2,如果给一个答案,给目标一个小段的长度,很容易判断是否到K个了。
    3,具有单调性,目标小段越长,那能切出的段数越少,目标小段越短,能切出的段数越多。而最终需要K个,从而很容易判断一个答案行不行。

    一看求啥,求最长长度,最长?这不,关门打狗,模板2! !

    那,判断条件?模板2,如果满足判断,l=mid。啥叫满足呢?那肯定是满足需要的段数了呗!

    code:

    #include<iostream>
    using namespace std;
    
    const int N=1e5+10;
    long long a[N],n,m,sum,maxa;
    
    int check(int mid)
    {
    	int sum=0;
    	for(int i=1;i<=n;i++){
    		sum+=a[i]/mid;
    	}
    	if(sum>=m) return 1; //总段数大于等于所需要的 
    	return 0;
    } 
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i],sum+=a[i];
    		if(a[i]>maxa) maxa=a[i];  
    	}
    	
    	if(sum<m){cout<<0;return 0;} //先判断是否有解 
    	
    	int l=1,r=maxa;
    	while(l<r) //模板2 
    	{
    		int mid=l+r+1>>1;
    		if(check(mid)) l=mid; 
    		else r=mid-1;
    	}
    	cout<<l;
    	return 0;
    }
    

    是不是感觉很有意思?

    再来看个经典的

    例2——跳石头

    在这里插入图片描述

    分析:看题,这是啥?最短距离的最大值!这不就是二分答案的典型特征?还想啥,二分!
    求最大?上模板2!! 那,判断条件?

    这时候就要注意了,我们二分的是最短距离,通过二分将这个最短距离(答案)最大化。那我们判断的时候肯定要保证mid是最短距离。

    如何保证?我们要求抽过石头剩下的石头中,两个石头间的最短距离为mid,那就要保证剩下的任意两个间距都要大于等于mid。要保证这个,那就只能挑间距大于等于mid的石头跳,中间的石头都将会被抽走。

    最后,计数可以被抽走的石头。如果可以被抽走的石头个数小于等于需要抽的M个了,就说明满足条件。因为:既然抽了小于M个都能满足剩下的石头中,两石头间的距离都大于等于mid了,那抽M个,更能满足!

    有点晕?没关系!看了代码就懂了!

    code:

    #include<iostream>
    using namespace std;
    
    const int N=50010;
    int a[N],n,len,m,mina=1e9+1,b[N];
    
    int check(int mid)	//检查,是否最短距离为mid,如果两石头间距小于mid,不满足,移走 
    {
    	int cnt=0;
    	int i=0,now=0;	//i表示目标位置,now为当前位置。
    	while(i<n+1){
    		i++;
    		if(a[i]-a[now]<mid){ //两石头间距离小于mid,mid不是最短距离,不满足,移走该石头 
    			cnt++;
    		}
    		else{	//符合,跳过去 
    			now=i;
    		}
    	}
    	if(cnt<=m) return 1;	//移走的石头个数小于 M,就能保证了任意两剩下的石头间距大于等于最短距离mid,那移走M个,更能保证 
    	return 0;
    }
    
    int main(){
    	cin>>len>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		if(a[i]<mina) mina=a[i];
    	}
    	a[0]=0,a[n+1]=len; //首尾都有石头
    	
    	if(n==0){ //特判掉起点和终点之间没有石头的情况,可以想一下为什么。评论区中有答案。感谢 luojias 同学的hack数据!
    		cout<<len; return 0;
    	}
    
    	//二分答案:检查每一个答案(最短距离mid)是否符合要求 
    	long long l=1,r=1e10;
    	while(l<r) //模板2
    	{
    		int mid=l+r+1>>1;
    		if(check(mid)) l=mid; //要的是距离的最大,所以尽可能地往右走 
    		else r=mid-1;
    	}
    	cout<<l;
    	return 0;
    } 
    

    还没懂?没关系,我们再看一题!

    例3——丢瓶盖

    分析:距离最近的2个瓶盖距离最大? 最短距离的最大值! 二分!!

    看——求最大值,模板二!

    判断条件check:与上题不同的是,这题是保证拿走的那些瓶盖之间的最短距离最大(上题是保证剩下的石头最短距离最大,这两个容易混淆。是我没错了… ),那么,遍历的时候,只要满足这次和上次拿的那个瓶盖间距大于等于mid,就可以拿了。这样就保证了我们找的最短距离mid是最短的间距。

    最后如果拿出的总瓶盖数大于等于目标值,就说明满足判断。因为:既然拿了超过目标值就能满足拿走的瓶盖间距大于等于mid,那拿目标值(B)个,肯定更能满足!

    code:

    #include<iostream>
    #include<algorithm>
    using namespace std;
    
    const int N=100010;
    int a[N],n,m,maxa;
    
    //注意:这是拿出来的那些里,mid为最短距离,和跳石头不同的是,跳石头是在留下的里面,mid为最短距离 
    int check(int mid)
    {
    	//now为最后一次拿的瓶盖位置,i为当前遍历的位置
    	int i=1,now=1,cnt=0; 注意:第一个瓶盖必选,才能保证剩下的距离最大,从而挑出的瓶盖间最短距离最大化 
    	while(i<n)
    	{
    		i++;
    		if(a[i]-a[now]>=mid){ //保证拿走的瓶盖间距大于等于mid,才拿这个瓶盖,否则不能保证mid为最短距离
    			now=i,cnt++;
    		}
    	}
    	if(cnt+1>=m) return 1;	//如果拿出的总个数大于等于m,都能保证拿走的瓶盖间距大于等于mid,那拿出来m个,肯定也能满足!!
    	return 0;
    
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i];
    		if(a[i]>maxa) maxa=a[i]; 
    	}
    	sort(a+1,a+n+1);
    	
    	int l=0,r=maxa;
    	while(l<r) //模板2
    	{
    		int mid=l+r+1>>1;
    		if(check(mid)) l=mid;
    		else r=mid-1;
    	}
    	cout<<l<<endl;
    	
    }
    

    做了上面两题,我们差不多又可以总结出规律了,心里是不是有点小激动?

    最大值最小,最小值最大 类 问题解题方向:

    最短距离最大化问题:保证任意区间距离要比最短距离mid大或相等(这样,mid才是最短距离)即:区间的距离>=mid

    最长距离最小化问题:保证任意区间距离要比最大距离mid小或相等(这样,mid才是最大距离)即:区间的距离<=mid

    哈哈哈,是不是太有趣啦?

    快快,趁热打铁,再来!!

    例4——数列分段 Section II

    在这里插入图片描述
    在这里插入图片描述分析:没错,这次是最大值最小!
    求最小值? 哎对,模板1!
    判断条件要保证:每一段的和都小于等于最大值。也就是说,只要这一段的和加上下一个值大于最大值了,那下一个值加不得,得分段!接着段数++;
    最后,统计出的总段数(cnt+1)小于等于目标值了,那就算满足;因为,既然分了小于目标值个段都能保证每段的和小于等于最大值,那么分目标值个段肯定还能保证!

    还有一个小细节:l,和 r 的初始化。
    所有段中的最大和肯定大于等于数列中的最大值(因为最大值最少单成一段,那所有段中的最大的和肯定要大于等于最大值),所以l要初始化为maxa。
    同样,所有段中和的最大值,最大不过数列中的所有值的和。

    code:

    #include<iostream>
    using namespace std;
    
    const int N=100010;
    typedef long long ll;
    ll a[N],n,m,summ,mina=1e9+1,maxa;
    
    int check(int mid)
    {
    	ll cnt=0,sum=0;
    	for(int i=1;i<=n-1;i++)
    	{
    		sum+=a[i];
    		if(sum+a[i+1]>mid) cnt++,sum=0; //不能满足 "区间间距小于最大距离",那就分段 
    	}
    	if(cnt+1<=m) return 1;	//总的段数小于等于需要的段数,这样都能满足mid为每段的最大值,那么多分几段,肯定还能满足 
    	return 0;
    }
    int main(){
    	cin>>n>>m;
    	for(int i=1;i<=n;i++){
    		cin>>a[i],summ+=a[i];	
    		if(a[i]<mina) mina=a[i];
    		if(a[i]>maxa) maxa=a[i];
    	}
    	
    	int l=maxa,r=summ;	//l要设为maxa,所有段的最大值肯定大于等于maxa 
    	while(l<r)
    	{
    		int mid=l+r>>1;
    		if(check(mid)) r=mid; //求的是最大值的最小,故尽量往左来 
    		else l=mid+1;
    	}
    	cout<<l;
    	return 0;
    } 
    

    好啦,至此,二分答案你就差不多掌握了。方法说的都是实打实的;
    最后,在给出几道练习题吧:
    1、进击的奶牛
    2、路标设置
    3、最佳牛围栏
    4、kotori的设备

    本文的课后练习题的答案在这个博客里。

    相信看到这的你一定收获了不少吧。

    讲的有点多,看不完的话可以先收藏。如果有没讲到的,后续会再更新。

    有哪里不明白的话欢迎留言或评论,相互讨论,共同进步!

    哪里写的有问题的话,还请大佬们不吝赐教。

    参考博客:https://www.it610.com/article/1292865348768440320.htm

    展开全文
  • 二分查找】详细图解

    万次阅读 多人点赞 2021-04-24 15:59:45
    二分查找 文章目录二分查找1. 简介2. 例子3. 第一种写法(左闭右闭)3.1 正向写法(正确演示)3.2 反向写法(错误演示)4. 第二种写法(左闭右开)4.1 正向写法(正确演示)4.2 反向写法(错误演示)5. 总结 写在前面...

    在这里插入图片描述

    二分查找

    写在前面:

    (一)二分法的思想十分容易理解,但是二分法边界处理问题大多数人都是记忆模板,忘记模板后处理边界就一团乱(👁:“我懂了”, ✋ :"你懂个🔨"​)因为我此前也是记忆模板,所以现在想通过一边学习,一边将所学记录成博客教出去(费曼学习法),希望以后能自己推导出边界如何处理,而不仅仅是记忆模板。欢迎一起交流学习,如有看法不一样之处也欢迎留言一起讨论!

    (二)我主要解释了二分法的左闭右闭区间,左闭右开区间两种写法,并且每个写法都举了相应的反例,范围写错的话可能会出现的错误等…

    1. 简介

    故事分享🏬:

    有一天小明到图书馆借了 N 本书,出图书馆的时候,警报响了,于是保安把小明拦下,要检查一下哪本书没有登记出借。小明正准备把每一本书在报警器下过一下,以找出引发警报的书,但是保安露出不屑的眼神:你连二分查找都不会吗?于是保安把书分成两堆,让第一堆过一下报警器,报警器响;于是再把这堆书分成两堆…… 最终,检测了 logN 次之后,保安成功的找到了那本引起警报的书,露出了得意和嘲讽的笑容。于是小明背着剩下的书走了。 从此,图书馆丢了 N - 1 本书。

    保安怎么知道只有一本书📖没有登记出借,万一全部都没有登记呢​?

    这个故事其实说出了二分查找需要的条件

    • 用于查找的内容逻辑上来说是需要有序的
    • 查找的数量只能是一个,而不是多个

    比如在一个有序的数组并且无重复元素的数组中,例如[1, 2, 3, 4, 5, 6],需要查找3的位置就可以使用二分查找。

    在二分查找中,目标元素的查找区间的定义十分重要,不同的区间的定义写法不一样

    因为查找的区间是不断迭代的,所以确定查找的范围十分重要,主要就是左右区间的开和闭的问题,开闭不一样,对应的迭代方式也不一样,有以下两种方式:

    • 左闭右闭[left, right]

    • 左闭右开[left, right)

    2. 例子

    这是一个使用二分查找的例题

    题目如下:

    给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。

    示例一:

    输入: nums = [-1,0,3,5,9,12], target = 9
    输出: 4
    解释: 9 出现在 nums 中并且下标为 4

    示例二:

    输入: nums = [-1,0,3,5,9,12], target = 2
    输出: -1
    解释: 2 不存在 nums 中因此返回 -1

    提示:

    • 你可以假设 nums 中的所有元素是不重复的。
    • n 将在 [1, 10000]之间。
    • nums 的每个元素都将在 [-9999, 9999]之间。

    出自704. 二分查找 - 力扣(LeetCode) (leetcode-cn.com)

    二分法的思想很简单,因为整个数组是有序的,数组默认是递增的。

    • 首先选择数组中间的数字和需要查找的目标值比较
    • 如果相等最好,就可以直接返回答案了
    • 如果不相等
      • 如果中间的数字大于目标值,则中间数字向右所有数字都大于目标值,全部排除
      • 如果中间的数字小于目标值,则中间数字向左所有数字都小于目标值,全部排除

    二分法就是按照这种方式进行快速排除查找的

    tips:

    不用去纠结数组的长度是奇数或者偶数的时候,怎么取长度的一半,以下说明,可以跳过。

    当数组的长度为奇数的时候

    是奇数的情况很简单,指向中间的数字很容易理解,如果需要查找的数字为29

    因为29大于中间的数字大于11,所以左边的所有数字全部排除

    当数组的长度为偶数的时候

    这个时候中间的数字两边的数字数量就不一样了(刚开始学习二分法的时候我经常纠结这个问题,和另外一个长度除2得到的是最中间的数吗的问题,我相信不止我一个人纠结过……但其实这是同一个问题,每次长度除2,如果长度为奇数,得到的中间的数字两边数字数量相同,如果长度为偶数就为上图中间的数字两边的相差为 1)

    但是千万不要一直纠结中间的数字两边的数字数量不一样这个问题,因为:

    • 两边数量不一样是一定会出现的情况
    • 但是这种情况并不影响我们对中间数字和目标数字大小关系的判断
      • 只要中间数字大于目标数字,就排除右边的
      • 只要中间数字小于目标数字,就排除左边的

    所以数组长度是偶数还是奇数这个真的不重要,不影响怎么排除的问题,无非是多排除一个数字或者少排除一个数字

    • 真正影响的是中间那个数字到底该不该加入下一次的查找中,也就是边界问题

    3. 第一种写法(左闭右闭)

    二分法最重要的两个点:

    • while循环中 left 和 right 的关系,到底是 left <= right 还是 left < right
    • 迭代过程中 middle 和 right 的关系,到底是 right = middle - 1 还是 right = middle

    3.1 正向写法(正确演示)

    第一种写法:每次查找的区间在[left, right](左闭右闭区间),根据查找区间的定义(左闭右闭区间),就决定了后续的代码应该怎么写才能对。因为定义 target 在[left, right]区间,所以有如下两点:

    • 循环条件要使用while(left <= right),因为当(left == right)这种情况发生的时候,得到的结果是有意义的
    • if(nums[middle] > target) , right 要赋值为 middle - 1, 因为当前的 nums[middle] 一定不是 target ,需要把这个 middle 位置上面的数字丢弃,那么接下来需要查找范围就是[left, middle - 1]

    代码如下:

    int search(int nums[], int size, int target) //nums是数组,size是数组的大小,target是需要查找的值
    {
        int left = 0;
        int right = 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 {	//既不在左边,也不在右边,那就是找到答案了
                return middle;
            }
        }
        //没有找到目标值
        return -1;
    }
    

    下面图解算法的实现过程,建议将代码复制到一个文本编辑器中,边看代码边看图。或者我直接准备了图片,保存下来打开看就好了。

    首先看一个数组,需要对这个数组进行操作。需要对33进行查找的操作,那么target 的值就是33

    • 首先,对 left 的值和 right 的值进行初始化,然后计算 middle 的值
      • left = 0, right = size - 1
      • middle = (left + (right - left) / 2 )
    • 比较 nums[middle] 的值和 target 的值大小关系

      • if (nums[middle] > target),代表middle向右所有的数字大于target
      • if (nums[middle] < target),代表middle向左所有的数字小于target
      • 既不大于也不小于就是找到了相等的值
    • nums[middle] = 13 < target = 33,left = middle + 1

    • 见下图:

    • 循环条件为 while (left <= right)

    • 此时,left = 6 <= right = 11,则继续进行循环

    • 当前,middle = left + ((right - left) / 2),计算出 middle 的值

    • 计算出 middle 的值后,比较 nums[middle] 和 target 的值,发现:

      • nums[middle] = 33 == target = 33,找到目标

    3.2 反向写法(错误演示)

    对应第一种正向的写法,我们把循环条件修改看看会发生什么事

    • 原查找区间 [left, right]
    • 原循环条件是 while (left <= right)

    修改后题目对应的条件:

    • 查找区间不变,仍然是[left, right]
    • 查找数字为27 (target = 27)
    • 循环条件修改为while (left < right)

    代码:

    int search(int nums[], int size, int target) 
    {
        int left = 0;
        int right = size - 1;	
        while (left < right) {	//left <= right 修改为 left < right,其他不变
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) {
                right = middle - 1;
            } else if (nums[middle] < target) {
                left = middle + 1;
            } else {	
                return middle;
            }
        }
        //没有找到目标值
        return -1;
    }
    

    代码图片,边看模拟过程边看代码哦!

    好了,现在开始用图片模拟过程

    • 初始化一个数组,计算 middle 的值
    • 根据计算的 middle 值确定 nums[middle]
    • 因为nums[middle] = 13 < target = 27,所以left = middle + 1
    • 继续计算 middle 的值
    • 因为 nums[middle] = 33 > target = 27,所以 right = middle - 1
    • 接着计算 middle 的值
    • 因为 nums[middle] = 22 < target = 27,此时 left = middle + 1,此时 left = right,而循环条件为while (left < right),所以还未找到27 的情况下算法就跳出了循环,返回 -1

    4. 第二种写法(左闭右开)

    4.1 正向写法(正确演示)

    第二种写法:每次查找的区间在 [left, right),(左闭右开区间), 根据区间的定义,条件控制应该如下:

    • 循环条件使用while (left < right)
    • if (nums[middle] > target), right = middle,因为当前的 nums[middle] 是大于 target 的,不符合条件,不能取到 middle,并且区间的定义是 [left, right),刚好区间上的定义就取不到 right, 所以 right 赋值为 middle。

    代码如下:

    int search(int nums[], int size, int target)
    {
    	int left = 0;
    	int right = size; //定义target在左闭右开的区间里,即[left, right)
    	while (left < right) {	//因为left = right的时候,在[left, right)区间上无意义
    		int middle = left + ((right - left) / 2);
    		if (nums[middle] > target) {
    			right = middle; //target 在左区间,在[left, middle)中 
    		} else if (nums[middle] < target) {
    			left = middle + 1;
    		} else {
    			return middle;
    		}
    	} 
        // 没找到就返回-1
    	return -1;
    }
    

    代码图片:保存下来边看代码边看图片演示过程

    • 需要查找的值为3

    第一步是初始化 left 和 right 的值,然后计算 middle 的值

    • left = 0, right = size
    • 循环条件while (left < right)

    因为是左闭右开区间,所以数组定义如下:

    • 计算 middle 的值,
    • 比较 nums[middle] 和 target 的大小:因为 nums[middle] = 22 > target = 3
    • 所以 right = middle
    • 符合循环的条件,接着计算 middle 的值
    • 比较 nums[middle] 和 target 的大小:因为 nums[middle] = 9 > target = 3
    • 所以 right = middle
    • 符合循环的条件,继续计算 middle 的值
    • 比较 nums[middle] 和 target 的大小关系:因为nums[middle] = 0 < target = 3
    • 所以 left = middle + 1

    在这里插入图片描述

    • 符合循环条件,接着计算 middle 的值
    • 比较 nums[middle] 和 target 的关系:nums[middle] = 3 == target = 3
    • 成功找到 target

    4.2 反向写法(错误演示)

    对应第二种正确的写法,照样把循环条件修改,看会发生什么事

    正确的写法中条件为:

    • 查找原区间 [left, right)
    • 循环条件为 while (left < right)

    修改后题目对应的条件:

    • 查找区间不变,仍然是 [left, right)

    • 循环条件修改为:while (left <= right)

    • 查找的数字为26(数组中不存在这个数字!!!

    代码:

    int search(int nums[], int size, int target)
    {
    	int left = 0;
    	int right = size; 
    	while (left <= right) {	//条件left < right 修改为 left <= right
    		int middle = left + ((right - left) / 2);
    		if (nums[middle] > target) {
    			right = middle; 
    		} else if (nums[middle] < target) {
    			left = middle + 1;
    		} else {
    			return middle;
    		}
    	} 
        // 没找到就返回-1
    	return -1;
    }
    

    代码图片:(记得边看边保存图片代码边看图片演示哦!)

    以下是演示全过程:

    • 同样,开始初始化一个数组
    • 先计算 middle 的值
    • 判断 nums[middle] 和 target 的大小关系:nums[middle] = 22 < target = 26
    • left = middle + 1 (其实这里nums[left] 已经等于27,26不可能找到,接下去就看算法是否能够知道数组中不存在26并且返回-1 了)
    • 符合循环条件,计算 middle 的值
    • 判断 nums[middle] 和 target 的大小关系:nums[middle] = 57 > target = 26
    • right = middle
    • 满足循环条件,接着计算 middle 的值
    • 比较 nums[middle] 和 target 的大小关系:nums[middle] = 33 > target = 26
    • right = middle
    • 符合循环条件,继续计算 middle 的值
    • 比较 nums[middle] 和 target 大小关系,因为 nums[middle] = 27 > target = 26,
    • 所以 right = middle,自此,left 和 right 相遇,但是循环条件被我们修改成 while (left <= right) 会接着做循环
    • 接下来就是死循环

    • 因为 middle = left + ((right - left) / 2),当 left = right 的时候,middle 的值不会继续改变

    • middle 不继续改变,由于right = middle,right 也不会改变,所以三个数字自此开始不会继续改变

    • 循环条件 while (left <= right) 却仍然满足,不会跳出循环

    • 死循环……

    5. 总结

    二分法最重要的两个点,就是循环条件和后续的区间赋值问题

    因为两者是相互联系,相互影响的,所以就需要两者统一,如果两者不统一,就会出现问题

    所以循环条件和赋值问题必须统一,也就是循环不变量。

    相关题目推荐:

    本文相关信息:

    • 算法学习自微信公众号:“代码随想录”
    • 画图软件:Diagrams
    • 代码生成图片软件:Carbon

    ❤️完结撒花❤️

    展开全文
  • 二分查找

    千次阅读 2020-12-28 22:53:17
    二分查找法(Binary Search)算法,也叫折半查找算法。二分查找针对的是一个有序的数据集合,查找思想有点类似于分治思想。每次都通过跟区间的中间元素对比,将带查找的区间缩小为之前的一半,直到找到要查找的元素...
  • Golang语言实现 实现二分查找,二分左侧查找,二分右侧查找,直接贴代码,其中包括注释含义 package algorithmProject import ( "fmt" "testing" ) func TestBinarySearch(t *testing.T) { ///////////下标:...
  • 二分查找【详解】

    万次阅读 多人点赞 2022-04-16 13:19:45
    主要介绍:二分查找的简单思路,为什么必须在有序的前提下才能使用二分查找,该怎么用C程序来实现二分查找二分查找的局限性。 目录 简单思路 前提条件 编写程序 总结 简单思路 当我们要从一个序列中查找一个...
  • 二分查找(折半查找)详解

    千次阅读 多人点赞 2021-01-10 01:05:54
    二分查找的引入 说到二分查找相信大家都很熟悉,最经典的例子就是猜数字问题: 从1到100中,随机抽取一个数字。现在然你猜测这个数字究竟是多少,如果你猜的数字大于目标值,则会提示你该值大了;反之则会提示你该...
  • 算法分析与设计 二分查找

    千次阅读 2021-05-19 20:05:28
    算法分析与设计 二分查找 二分查找的基本概念 ​ 二分查找是一种在有序数组中查找某一特定元素的查找算法。这种查找方法将查找的时间复杂度从原本的线性时间提升到了对数时间范围,大大缩短了搜索时间。 ​ 二分查找...
  • 二分查找(折半查找)总结

    千次阅读 多人点赞 2022-03-23 10:49:55
    二分查找(折半查找)总结 ** 文章目录二分查找(折半查找)总结一、基本概念二、编写代码1.二分查找2.测试代码三、输出结果四、总结评价 一、基本概念 二分查找也叫折半查找,是一种效率比较高的查找方法。但是...
  • 可以通过线性查找和二分查找来完成,但是要猜测哪个更快。 为什么? 如果你最近参加过面试,你就会知道二分查找是面试官的最爱。 您为什么要花时间学习二分查找? C ++编程朋友可能已经告诉过您。 Python很慢。 您想...
  • 1.线性查找 有一个数列: {1,8, 10, 89, 1000, 1234} ,判断数列中是否包含此名称【顺序查找】 要求: 如果找到了,就提示找到,并给出下标值。 package com.szh.search; /** * 线性查找 */ public class ...
  • C++实现二分查找

    千次阅读 2021-10-24 00:59:40
    // 二分查找函数 Result BinarySearch(int* a, const int n, const int x) { // 初始化结果存储结构 Result result; // 在数组 a[0], ..., a[n-1] 中寻找 x int left = 0, right = n-1, middle = (left + right) / ...
  • 二分查找---C++实现

    千次阅读 2022-03-23 15:31:11
    二分查找题目1:704.二分查找题目2:35. 搜索插入位置题目3:34. 在排序数组中查找元素的第一个和最后一个位置题目4:69. x 的平方根题目5:367. 有效的完全平方数 题目1:704.二分查找 leetcode 704.二分查找 给定...
  • Java实现二分查找

    千次阅读 2021-03-23 13:35:53
    本教程将介绍Java中的进制搜索和递归进制搜索,以及其算法,实现和Java Binary Seach代码示例: Java中的进制搜索是一种用于在集合中搜索目标值或键的技术。它是一种使用“分而治之”技术搜索密钥的技术。 ...
  • java实现二分查找

    千次阅读 2021-05-28 11:31:48
    Java实现数组二分查找 给定一个有序的int数组,指定查找元素,要求查找该元素在给定数组中的位置。 假定给定数组为:[1, 3, 5, 7, 9, 11, 13, 15]。 思路分析 所谓二分查找,就是每次查找都取查找范围二分之一处...
  • 二分查找的递归实现思路分析代码实现 思路分析 1、确定该序列的中间的下标mid: mid = (left + right)/2; 2、让需要查找的数findVal 与 arr[mid]进行比较: (1)findVal > midVal,则进行向右递归,查找...
  • 详解二分查找

    千次阅读 2021-09-01 15:24:46
    为什么要使用二分查找 当有一个排好顺序的数组,我们需要知道我们要找的值是否在当前数组中,那么我们就需要自己实现一个查找的方法来进行实现,那么如果我们找的数在最后一个位置n处,假设这个n非常大,那么我们...
  • 二分查找算法

    千次阅读 2021-05-09 20:40:50
      二分查找(Binary Search)也称折半查找,它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。   查找过程: 首先,假设表中元素是按升序排列,将表...
  • (6)二分查找及其应用场景

    千次阅读 2021-09-13 22:46:45
    数据结构&算法模块总结 (1)复杂度分析原理与方法 ...1.传统二分查找模板问题 public int bsearch(int[] a, int n, int value) { int low = 0; int high = n - 1; while (low <= high) { int mid = (l
  • 二分查找的时间复杂度以及算法

    千次阅读 2021-11-02 20:11:13
    ​ 给定一个规模为n的按照数字从小到大排序的...1、计算数据规模为n二分查找的时间复杂度 循环次数 剩下的数据规模 第一次查找: T(1) = n/2 第二次查找: T(2) = n/2^2 第三次查找: T(3) = n/2^3 … 第M次查找: T(M)
  • C语言 递归函数实现二分查找

    千次阅读 2021-08-19 10:46:27
    C语言 递归函数实现二分查找 欢迎使用Markdown编辑器 你好! 这是你第一次使用 Markdown编辑器 所展示的欢迎页。如果你想学习如何使用Markdown编辑器, 可以仔细阅读这篇文章,了解一下Markdown的基本语法知识。 新的...
  • 二分查找算法及其变种详解

    千次阅读 多人点赞 2019-02-15 21:11:47
    二分查找(Binary Search)算法,也叫折半查找算法,它的思想非常简单,在生活中随处可见(比如:猜字游戏),但这看似简单的算法,实际却没那么容易掌握透彻。 二分查找针对的是一个有序的数据集合,查找思想有点...
  • 二分查找(Java实现)

    千次阅读 2022-03-28 18:37:57
    二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。 在我学习过程中,遇到了二分查找的相关问题,所以想简单...
  • java二分查找

    千次阅读 2022-04-15 21:37:11
    java的二分查找
  • c语言实现二分查找

    千次阅读 多人点赞 2022-01-16 17:55:05
    目录 一.前言 二.二分查找法 1.什么是二分查找法 2.如何用c语言来实现二分查找法 ...三....一....假如今天我们需要在一个有序的数组中来寻找一个数的下标,就用"1,2,3,4,5,6,7,8,9"这九个数组成的数组来...二分查找

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 796,821
精华内容 318,728
关键字:

二分查找

友情链接: JJ.rar