image.png
动图演示
1608987789-UOOWmi-file_1608987789042.gif

  1.  public static int binarySearch(int[] nums,int target,int left, int right) {
  2.         //这里需要注意，循环条件
  3.         while (left <= right) {
  4.             //这里需要注意，计算mid
  5.             int mid = left + ((right - left) >> 1);
  6.             if (nums[mid] == target) {
  7.                 return mid;
  8.             }else if (nums[mid] < target) {
  9.                 //这里需要注意，移动左指针
  10.                 left  = mid + 1;
  11.             }else if (nums[mid] > target) {
  12.                 //这里需要注意，移动右指针
  13.                 right = mid - 1;
  14.             }
  15.         }
  16.         //没有找到该元素，返回 -1
  17.         return -1;
  18.     }

二分查找容易出错的地方：

  1. 计算 mid 时 ，不能使用 （left + right ）/ 2,否则有可能会导致溢出

  2. while (left < = right) { } 注意括号内为 left <= right ,而不是 left < right ，我们继续回顾刚才的例子，如果我们设置条件为 left < right 则当我们执行到最后一步时，则我们的 left 和 right 重叠时，则会跳出循环，返回 -1，区间内不存在该元素，但是不是这样的，我们的 left 和 right 此时指向的就是我们的目标元素 ，但是此时 left = right 跳出循环

  3. left = mid + 1,right = mid - 1 而不是 left = mid 和 right = mid。我们思考一下这种情况,见下图，当我们的target 元素为 16 时，然后我们此时 left = 7 ，right = 8，mid = left + (right - left) = 7 + (8-7) = 7，那如果设置 left = mid 的话，则会进入死循环，mid 值一直为7 。

搜索插入位置

image.png

  1. class Solution {
  2.     public int searchInsert(int[] nums, int target) {
  3.         int left=0;
  4.         int right=nums.length-1;
  5.         while(left<=right){
  6.             int mid=left+(right-left)/2;
  7.             if(nums[mid]==target){
  8.                 return mid;
  9.             }else if(nums[mid]<target){
  10.                 left=mid+1;
  11.             }else
  12.                 right=mid-1;
  13.         }
  14.         return left; //当left,mid,right在同一个元素上，发现比这个target小，那么left+1，下一次循环跳出，此时left的位置为插入的位置
  15.     }
  16. }

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

image.png
1.gif

  1. class Solution {
  2.     public int[] searchRange(int[] nums, int target) {
  3.         int upper = UpRange(nums,target);
  4.         int downer = DownRange(nums,target);
  5.         if(downer<upper){
  6.              return new int[]{-1,-1};
  7.         }
  8.         return new int[]{upper,downer}; 
  9.     }
  10.     private int UpRange(int[] nums,int target){
  11.         int left = 0, right = nums.length - 1;
  12.         while (left <= right) {
  13.             int mid = left + ((right - left)/2);
  14.             if(target<=nums[mid]){
  15.                 right=mid-1;
  16.             }else{
  17.                 left=mid+1;
  18.             }
  19.         }
  20.         return left;
  21.     }
  22.     private int DownRange(int[] nums,int target){
  23.         int left = 0, right = nums.length - 1;
  24.         while (left <= right) {
  25.             int mid = left + ((right - left)/2);
  26.             if(target>=nums[mid]){
  27.                 left=mid+1;
  28.             }else{
  29.                 right=mid-1;
  30.             }
  31.         }
  32.         return right;
  33.     }
  34. }

找出第一个大于目标元素的索引

我们在上面的变种中，描述了如何找出目标元素在数组中的上下边界，然后我们下面来看一个新的变种，如何从数组或区间中找出第一个大于或最后一个小于目标元素的数的索引，例 nums = {1,3,5,5,6,6,8,9,11} 我们希望找出第一个大于 5的元素的索引，那我们需要返回 4 ，因为 5 的后面为 6，第一个 6 的索引为 4，如果希望找出最后一个小于 6 的元素，那我们则会返回 3 ，因为 6 的前面为 5 最后一个 5 的索引为 3。好啦题目我们已经了解，下面我们先来看一下如何在数组或区间中找出第一个大于目标元素的数吧。

找出第一个大于目标元素的数，大概有以下几种情况

1.数组包含目标元素，找出在他后面的第一个元素

2.目标元素不在数组中，数组内的部分元素大于它，此时我们需要返回第一个大于他的元素

3.目标元素不在数组中，且数组中的所有元素都大于它，那么我们此时返回数组的第一个元素即可

4.目标元素不在数组中，且数组中的所有元素都小于它，那么我们此时没有查询到，返回 -1 即可。

既然我们已经分析完所有情况，那么这个题目对咱们就没有难度了，下面我们描述一下案例的执行过程
image.png
那么我们看一下，当 target = 0时，程序应该怎么执行呢？
image.png

  1. public static int lowBoundnum(int[] nums,int target,int left, int right) {
  2.         while (left <= right) {
  3.             int mid = left + ((right - left) >> 1);
  4.             if(nums[mid]>target){
  5.                 if(nums[mid-1]<=target||mid==0){  
  6.                     return mid;    
  7.                 }
  8.                 else{
  9.                     right=mid-1;
  10.                 }
  11.             }else if(nums[mid]<=target){
  12.                 left=mid+1;
  13.             }
  14.         }
  15.     return -1;
  16.     }

如果nums[mid]大于target，测试一下mid的前一个数是否小于或等于target，如果是则mid肯定是该大于target的第一个元素。当mid为0说明数组的元素都比target大，即数组第一个数就是大于target的第一个元素。
为什么要小于等于，因为要找的元素是比target大，当nums[mid]等于target，还是需要继续往mid右边找第一个大于target的元素。

找出最后一个小于目标元素的索引

  1. public static int lowBoundnum(int[] nums,int target,int left, int right) {
  2.         while (left <= right) {
  3.             int mid = left + ((right - left) >> 1);
  4.             if(nums[mid]<target){
  5.                 if(nums[mid+1]>=target||mid==right){  
  6.                     return mid;    
  7.                 }
  8.                 else{
  9.                     left=mid+1;
  10.                 }
  11.             }else if(nums[mid]<=target){
  12.                 right=mid-1;
  13.             }
  14.         }
  15.     return -1;
  16.     }

leetcode33搜索旋转排序数组

image.png
数组虽然不是完全有序，但可以看成由两个有序数组，且第二个数组的最大值小于第一组的最小值，它们进行拼接得到的。
1608987789-aGIDWv-file_1608987789057.png

  • 首先我们想一下，mid的值会落在哪里？
    • 如果nums[mid]>=nums[left]，说明mid和left在同一个数组
    • 如果num[mid]<nums[left]，说明mid和right在同一个数组

1608987789-igcnYQ-file_1608987789058.png

  • 接着我们想一下target的值会有几种情况。
    • 当mid和left在同一数组
      • 落在mid的左边。例子中是target>=nums[left]&&target<=nums[mid]，此时我们让right=mid-1，让left和right都落在数组1中，下次再查找就是在数组1进行，该数组完全有序。
      • 落在mid的右边。两种情况，也就是target > nums[mid] || target < nums[left] 此时我们让 left = mid + 1即可，也是为了慢慢将left 和 right 指针赶到一个有序数组内。

1608987789-XiztGV-file_1608987789059.png

  • 当mid和right在同一数组，思路一样。
    • target <= nums[right] && target >= nums[mid]
    • target > nums[right] || target < nums[mid]

1608987789-DyzcDG-file_1608987789060.png

  1. class Solution {
  2.     public int search(int[] nums, int target) {
  3.         int left=0;
  4.         int right=nums.length-1;
  5.         while(left<=right){
  6.             int mid=left+(right-left)/2;
  7.              if (nums[mid] == target) {
  8.                 return mid;
  9.             }
  10.             if(nums[mid]>=nums[left]){
  11.                 //target 落在 left 和 mid 之间，则移动我们的right，完全有序的一个区间内查找
  12.                 if(nums[mid]>target&&nums[left]<=target){
  13.                     right=mid-1;
  14.                 }
  15.                 // target 落在right和 mid 之间，有可能在数组1， 也有可能在数组2
  16.                 else if(nums[mid]<target||target<nums[left]){
  17.                     left=mid+1;
  18.                 }
  19.             }
  20.             else if(nums[mid] < nums[left]){
  21.                 //有序的一段区间，target 在 mid 和 right 之间
  22.                 if (nums[mid] < target && target <= nums[right]) {
  23.                     left = mid + 1;
  24.                 // 两种情况，target 在left 和 mid 之间
  25.                 }else if(nums[mid]>target||target>nums[right]){
  26.                     right=mid-1;
  27.                 }
  28.             }
  29.         }
  30.         return -1;
  31.     }
  32. }

leetcode81. 搜索旋转排序数组 II

同leetcode31题一样，区别是数组中有重复的元素，那么会造成什么影响？
1608987789-rQkvNM-file_1608987789063 (1).jpg
当nums[mid]==nums[left]，会直接跳过目标元素。我们直接将left往右移动，直到nums[mid]!=nums[left]，那么就不会被重复元素所影响。

  1. class Solution {
  2.     public boolean search(int[] nums, int target) {
  3.           int left=0;
  4.         int right=nums.length-1;
  5.         while(left<=right){
  6.             int mid=left+(right-left)/2;
  7.              if (nums[mid] == target) {
  8.                 return true;
  9.             }
  10.             if(nums[mid]==nums[left]){
  11.                 left++;
  12.                 continue;
  13.             }
  14.             if(nums[mid]>nums[left]){
  15.                 //target 落在 left 和 mid 之间，则移动我们的right，完全有序的一个区间内查找
  16.                 if(nums[mid]>target&&nums[left]<=target){
  17.                     right=mid-1;
  18.                 }
  19.                 // target 落在right和 mid 之间，有可能在数组1， 也有可能在数组2
  20.                 else if(nums[mid]<target||target<nums[left]){
  21.                     left=mid+1;
  22.                 }
  23.             }
  24.             else if(nums[mid] < nums[left]){
  25.                 //有序的一段区间，target 在 mid 和 right 之间
  26.                 if (nums[mid] < target && target <= nums[right]) {
  27.                     left = mid + 1;
  28.                 // 两种情况，target 在left 和 mid 之间
  29.                 }else if(nums[mid]>target||target>nums[right]){
  30.                     right=mid-1;
  31.                 }
  32.             }
  33.         }
  34.         return false;
  35.     }
  36. }

leetcode 153 寻找旋转数组中的最小值

image.png

  • 有几种情况
    • nums[left]<nums[right]，数组完全有序，直接返回nums[left]即可
    • left和mid都在第一个数组，单调递增，所以不可能在这，需要移动left=mid+1往右边找
    • left在第一个数组，mid在第二个数组，那么最小值肯定在left和mid之间。有一个关键就是，mid有可能是最小值，所以right往左移动时，要注意别跳过mid的位置。right=mid。

1608987789-ZusSBJ-file_1608987789068.png
1608987789-lGwivB-file_1608987789077.png

  1. class Solution {
  2.     public int findMin(int[] nums) {
  3.         int left=0;
  4.         int right=nums.length-1;
  5.         while(left<=right){
  6.             if(nums[left]<=nums[right]){
  7.                 return nums[left];
  8.             }   
  9.             int mid=left+(right-left)/2;
  10.             if(nums[left]<=nums[mid]){
  11.                 left=mid+1;
  12.             }else if(nums[left]>nums[mid]){
  13.                 right=mid;
  14.             }
  15.         }
  16.         return -1;
  17.     }
  18. }

搜索二维矩阵

image.png
下面我们来看一下另外一种变体，如何在二维矩阵里使用二分查找呢？
其实这个很简单，只要学会了二分查找，这个完全可以解决，我们先来看一个例子

我们需要从一个二维矩阵中，搜索是否含有元素 7，我们如何使用二分查找呢？其实我们可以完全将二维矩阵想象成一个有序的一维数组，然后用二分，比如我们的二维矩阵中，共有 9 个元素，那定义我们的 left = 0，right = 9 - 1= 8，是不是和一维数组定义相同，然后我们求我们的 mid 值， mid = left +（(right - left) >> 1）此时 mid = 4 ，但是我们的二维矩阵下标最大是，nums[2,2]呀，你这求了一个 4 ，让我们怎么整呀。如果我们理解了二分查找，那么这个题目考察我们的应该是如何将一维数组的下标，变为 二维坐标。其实也很简单，咱们看哈，此时咱们的 mid = 4，咱们的二维矩阵共有 3行， 3列，那我们 mid =4，肯定在第二行，那么这个应该怎么求得呢?

我们可以直接用 （mid/列数），即可，因为我们 mid = 4，4 /3 = 1,说明在 在第二行，那如果 mid = 7 ，7/3=2，在第三行，我们第几行知道了，那么我们如何知道第几列呢？我们可以直接根据 （mid % 列数 ）来求得呀，比如我们此时 mid = 7，7%3 = 1，那么在我们一维数组索引为 7 的元素，其处于二维数组的第2列，大家看看下图是不是呀！

  1. class Solution {
  2.     public boolean searchMatrix(int[][] matrix, int target) {
  3.         if (matrix.length == 0) {
  4.                return false;
  5.            }
  6.         //行数
  7.         int row=matrix.length;
  8.         //列数
  9.         int col=matrix[0].length;
  10.         int left=0;
  11.         int right=row*col-1;
  12.         while(left<=right){
  13.             int mid=left+(right-left)/2;
  14.             //mid和row,col的关联
  15.             int rownum=mid/col;
  16.             int colnum=mid%col;
  17.             if(matrix[rownum][colnum]==target){
  18.                 return true;
  19.             }else if(matrix[rownum][colnum]<target){
  20.                 left++;
  21.             }else if(matrix[rownum][colnum]>target){
  22.                 right--;
  23.             }
  24.         }
  25.         return false;
  26.     }
  27. }