二分查找:手拿把掐!------Java代码实现

“没有天赋,那就不断重复.”

文章目录

• 前言
• • 文章有误敬请斧正 不胜感恩！
  • 模板一:(最基本的)
  • • • **左闭右闭:** [left,right]
  • 模板二:
  • • **左闭右开区间模板:**
    • 区间:左闭右开[left,right):
  • 模板三:
  • • 开区间模板:
    • (left,right)
  • 循环不变量:
  • 二分查找易错点:
  • 做题经验:
  • 疑问及解答：
  • • 我自己的一些问题：
    • ans:
• 题目中的:>,>=,<,<=情况的判断:(难点)
• • • 模板1:闭区间:找第一个>=targe的元素的下标
    • 模板2:左闭右开区间:
    • 模板3:开区间:
• 总结

前言

二分真是个好东西,她总是让我在清醒与糊涂间徘徊.
为了加深自己的记忆和印象,特此梳理了之前学习时的md笔记,又找出来回顾了一遍.
今天分享给大家,有好的想法和建议可以在评论区讨论或者私信我.
那么话不多说.我们来进入今天的学习吧!

文章有误敬请斧正 不胜感恩！

提示：以下是本篇文章正文内容，

模板一:(最基本的)

左闭右闭: [left,right]

while(left<=right)

class Solution {
  public int search(int[] nums, int target) {
	 int left=0;
	 int right=nums.length-1;
     int mid;
   	while(left<=right){
      mid=left+(right-left)/2;   //防止越界
   	 if(nums[mid]>target)
       {
         right=mid-1;//更新右边界nums[mid]已经确定了不是要查找的值,所以不必包含mid所以right更新为mid-1;
         //接下来搜索的区间是[left,mid-1];如果写成mid可能就死循环了.
        } 
       else if(nums[mid]<target){
         left=mid+1; //left同理     
        }
       if (nums[mid]==target)
          {
             return mid;
           }    
       }
      return -1;
      }
 }

模板 #1 是二分查找的最基础和最基本的形式。这是一个标准的二分查找模板，大多数高中或大学会在他们第一次教学生计算机科学时使用。模板 #1 用于查找可以通过访问数组中的单个索引来确定的元素或条件。

初始条件：left = 0, right = length-1
终止：left > right
向左查找：right = mid-1
向右查找：left = mid+1

为什么要写成mid=left+(right-left)/2，而不是mid=(left+right)/2。
因为会溢出！！此时的溢出指的是，mid可能会超出该数据类型的最大值
我们假定一个数据类型

uint8           //数据范围0~255
uint8 left,right,mid;

//假定

left = 200;
right = 250;

//则left+right =450 > 255，此时已经溢出了
//0001 1100 0010 因为只能存储8位，实际1100 0010=194
mid = (left+right)/2;  //此时实际mid=194/2

mid = left+(right-left)/2; //200+(250-200)/2 = 225
//此方法绝对不会溢出，最好写成这样

手打:

class Solution {

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

      return -1;

      }
    }

模板二:

左闭右开区间模板:

区间:左闭右开[left,right):

此时left=right在区间上不合法,所以

while(left<right)

class Solution {

  public int search(int[] nums, int target) {
	int left=0;
	int right=nums.length;//注意这一点因为右边是开区间所以right=nums.length时[left,right)  右边界还是从数组最后一项也就是nums.length-1开始的.
	int mid;
   	while(left<right){
     mid=left+(right-left)/2;
   	 if(nums[mid]>target)
     {
         right=mid;//由于if判断过了nums[mid]不符合题意,下一个搜索的左区间不包含mid 又因为右边是开区间 所以right=mid就可以了.
      }
    else if(nums[mid]<target){
         left=mid+1;
     }
      if (nums[mid]==target)
      {
           return mid;
       }    
    }

      return -1;

      }
    }

模板三:

开区间模板:

(left,right)

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

循环不变量:

区间的定义决定了边界处理:

二分查找易错点:

什么时候写left<=right?

什么时候写left<right?

if(nums[mid]>target){

什么时候写right=mid-1?

什么时候写right=mid?

}

做题经验:

如果题目要求是问某个值在不在区间里，用左闭右闭区间(while l<= r)，每个mid做大于、小于、等于三次判断，在等于时输出，循环结束未输出说明不在区间里；

如果题目要求“找到第一个大于/小于x的下标”，用左闭右开区间(while l < r)，每个mid做大于、小于等于两次判断，不在循环体里输出，循环结束返回l或r(l=r，不要返回mid)，就是所求下标。

疑问及解答：

我自己的一些问题：

1、为什么要有区间这个概念
2、为什么要确定右开还是右闭
3、中点怎么计算
4、中点防溢出怎么推导出来的
5、边界问题怎么处理
6、中点取偏左还是偏右

ans:

1、 因为二分查找的本质是在不断地变换区间里比较，并找到target
2、 因为在比较的过程中，会有一个对边界的处理，如果右边的边界参予比较就是闭，如果不参与就是开
3、 M - L = R - M 所以 M = (R + L ) /2
4、 L + (R - L)/2
5、 target < nums[mid]
当区间是右闭的时候，R参予比较的。M与target做了比较，再充当R时需要减1，所以新的 R = M - 1
当区间是右开的时候，R是不参予比较的。R = M
6、取偏左。当数组长度为 1 时，
nums = 【2】
L= 0, R = 1, M =1（右开后，取偏右）
因为 当区间是右开的时候，R是不参予比较，M永远都比较不出值

题目中的:>,>=,<,<=情况的判断:(难点)

模板1:闭区间:找第一个>=targe的元素的下标

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

模板2:左闭右开区间:

int left=0;
int right=nums.length;
int mid;
while(left<right){
   mid=left+(right-left)/2;
    if(nums[mid]>target){
        right=mid;
    }
    else if(nums[mid]<target){
        left=mid+1;
    }
    if(nums[mid]==target){
        return left;//return left或者right都可以;因为跳出循环的条件是left==right
    }
    return -1;
}

模板3:开区间:

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

//对于lower_bound3
1. 为什么left = -1，int right = nums.size()，而不是left = 0，int right = nums.size()-1？
答案：left = -1是为了mid能取到0。处理【8,8,8,8】 target=8的情况。
        nums.size()-1是为了mid能取到nums.size()。例如【7,7,7,7】 target=8的情况。
2. 为什么终止条件是left + 1 < right或者left + 1 != right？如果nums【mid】 >= target改变为nums【mid】 > target，终止条件应该变化吗？
答案：终止条件取决于nums【mid】 >= target，最终的答案的正确性与left和right的初始化值也有关。
3. start == nums.size() || nums【start】 != target是在处理哪些特殊情况？
答案：【7,7,7,7】 target=8 和 【3,4,6,7】 target = 5 
以上三个细节，环环相扣，例如【7,7,7,7】 target=8贯穿这三个细节。一定要自己输入例子，打印输出，慢慢理解这些细节，才算真正掌握了。就算我把这三个细节列出来，有时候也不一定就能理解，一定要自己从头到尾把细节扣一遍！！！

总结

在力扣游荡了也近一年了,看到各种天才,窥镜而自视,又弗如远甚.
像我这种没有天赋的人,二分都要研究好久的人,就只能靠不断地重复了.
“贯穿这三个细节。一定要自己输入例子，打印输出，慢慢理解这些细节，才算真正掌握了。就算我把这三个细节列出来，有时候也不一定就能理解，一定要自己从头到尾把细节扣一遍！！！”
以后再看到会不会觉得可笑.

今天的分享就到这里了,我们下篇文章再见.