二分查找模板全面总结

二分查找一般用于数据是有序的，我们要找到目标元素target,可以通过循环或者递归在每一次比较以后都把查找范围缩小一半，在剩下范围接着查找。接下来，我就来介绍一下二分查找。我总结了几种不同的清况用到的二分模板，不过大家还是要自己动手做题，多画图。

情形1

二分查找最基本的形式就是查找条件可以不需要和元素两侧进行比较来确定。

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

模板一的代码

int binarySearch(int[] nums, int target){ 
//如果数组为空或者长度为0，我们肯定找不到我们想要查找的元素
  if(nums == null || nums.length == 0)
    return -1;
//用左右指针来分别指向查找区间的左边界和右边界
  int left = 0, right = nums.length - 1;
  while(left <= right){ 
    // 这边涉及到数据溢出的问题
    int mid = left + (right - left) / 2;
    if(nums[mid] == target){  return mid; }
    else if(nums[mid] < target) {  left = mid + 1; }
    else {  right = mid - 1; }
  }

  // 
  return -1;
}

mid=(left+right)/2也可以，那为什么要写成mid=left+(right-left)/2; 这是为了防止数据溢出，假设数据最多存储范围是0~255。 left=200,right=240,这个时候在执行left+right的时候就已经超过范围了，所以为了防止数据溢出要写成mid=left+(right-left)/2

接下来通过实战来检验一下自己的学习成果

1.X的平方根

力扣–X的平方根

题目描述
给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

class Solution { 
    public int mySqrt(int x) { 
        //二分查找，由于是找算数平方根，所以肯定找得到
        //如果是0或1的话，直接返回
        if(x==0 || x==1) return x;
        //开始找
        int low=1;
        int high=x;
        int mid;
        while( low <=high){ 
            mid=(low + high)/2;
            if(mid> x /mid){ 
                high=mid-1;
            }else if(mid  < x/mid){ 
                low=mid+1;
            }else{ 
                return mid;          
            }
        }
        return high;
    }
}

为什么当条件不满足的时候，要返回low-1或high,我来说明一下，以目标元素是8为例。

2.搜索旋转排序数组

力扣-搜索旋转排序数组 题目描述

<font color="greeng">整数数组 nums 按升序排列，数组中的值 互不相同 。</font>

class Solution { 
    public int search(int[] nums, int target) { 
 int low = 0, high = nums.length - 1, mid = 0;
    while (low <=high) { 
        mid = low + (high - lo) / 2;
        if (nums[mid] == target) { 
            return mid;
        }
        // 先根据 nums[mid] 与 nums[low] 的关系判断 mid 是在左段还是右段 
        if (nums[mid] >= nums[low]) { 
            // 再判断 target 是在 mid 的左边还是右边，从而调整左右边界 low 和 high
            if (target >= nums[low] && target < nums[mid]) { 
                high = mid - 1;
            } else { 
                low = mid + 1;
            }
        } else { 
            if (target > nums[mid] && target <= nums[high]) { 
                low = mid + 1;
            } else { 
                high = mid - 1;
            }
        }
    }
    return -1;

  
    }
}

思路分析

情形2

查找条件需要访问元素的相邻的右边元素。 根据是否满足条件，来决定是向左还是向右。 保证查找空间在每一步中至少有 2 个元素。 需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。

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

1.第一个错误的版本

力扣-第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

这题就是要找到第一个出现错误的版本，如果当前版本正确，继续往下找之后的版本，如果当前版本错误，就看一下上一个版本是否正确，因为题目说出现错误版本，说明最后肯定有错误的版本。

/* The isBadVersion API is defined in the parent class VersionControl. boolean isBadVersion(int version); */

public class Solution extends VersionControl { 
    public int firstBadVersion(int n) { 
        int low=1;
        int high=n;
        int mid;
        while(low<high){ 
            mid=low+(high-low)/2;
           if(isBadVersion(mid)){ 
               //区间在[low,mid]
               high=mid;
           }else{ 
               low=mid+1;
           }
          
        }
       
        return low;
        
    }
}

2.寻找峰值

力扣-寻找峰值 我们可以看出来这题他肯定是有峰值的，我们可以用二分法，然后比较当前元素和相邻元素的大小，通过二分不断逼近。

class Solution { 
    public int findPeakElement(int[] nums) { 

        int low=0;
        int high=nums.length-1;
        int mid;
        while(low < high){ 
            mid=low+(high-low)/2;
            if(nums[mid] > nums[mid+1] ){ 
                //说明峰值在左边
                high=mid;
            }else{ 
                low=mid+1;
            }

        }
        return low;
                    
 

    }
}

3.寻找旋转排序数组中的最小值

这道题目挺有难度的，大家可以仔细想想

class Solution { 
    public int findMin(int[] nums) { 
  int low = 0;
        int high = nums.length - 1;
        while (low < high) { 
            int mid= low + (high - low) / 2;
            if (nums[mid] < nums[high]) { 
                high = mid;
            } else { 
                low = mid + 1;
            }
        }
        return nums[low];

 
    }
}

情形3

每一次查找范围中都有三个元素，要根据相邻元素来进行比较，从而判断向左还是向右 初始条件：left = 0, right = length-1 终止：left + 1 == right 对于我们初学的来来说，我们应该分别计算左边界和右边界，不要想着一下子解决，做题目要有耐心，不要想当然，多画图，可能画图分析自己就会了。

在排序数组中查找第一个和最后一个位置

在排序数组中查找第一个和最后一个位置 分析: 根据题目要求，我们知道目标元素在数组中可能出现多次，所以我们就需要找到这个元素的左边界和右边界，我们就可以使用两个二分查找来找到左边界和右边界。

class Solution { 
    public int[] searchRange(int[] nums, int target) { 
       int leftBorder = getLeftBorder(nums, target);
        int rightBorder = getRightBorder(nums, target);
        // 情况一
        if (leftBorder == -2 || rightBorder == -2) return new int[]{ -1, -1};
        // 情况三
        if (rightBorder - leftBorder > 1) return new int[]{ leftBorder + 1, rightBorder - 1};
        // 情况二
        return new int[]{ -1, -1};
    }

    int getRightBorder(int[] nums, int target) { 
        int left = 0;
        int right = nums.length - 1;
        int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
        while (left <= right) { 
            int middle = left + ((right - left) / 2);
            if (nums[middle] > target) { 
                right = middle - 1;
            } else {  // 寻找右边界，nums[middle] == target的时候更新left
                left = middle + 1;
                rightBorder = left;
            }
        }
        return rightBorder;
    }

    int getLeftBorder(int[] nums, int target) { 
        int left = 0;
        int right = nums.length - 1;
        int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
        while (left <= right) { 
            int middle = left + ((right - left) / 2);
            if (nums[middle] >= target) {  // 寻找左边界，nums[middle] == target的时候更新right
                right = middle - 1;
                leftBorder = right;
            } else { 
                left = middle + 1;
            }
        }
        return leftBorder;
    }
}