• 二分搜索篇

    二分搜索的三个常见应用场景

    寻找一个数（基本的二分搜索）

    • 这个场景是最简单的，可能也是大家最熟悉的，即搜索一个数，如果存在，返回其索引，否则返回 -1。
    1. int binarySearch(int[] nums, int target) {
    2.     int left = 0; 
    3.     int right = nums.length - 1; // 注意
    4.  
    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 if (nums[mid] > target)
    12.             right = mid - 1; // 注意
    13.     }
    14.     return -1;
    15. }

    • 因为索引大小为 nums.length 是越界的。我们这算法中使用的是 [left, right] 两端都闭的区间。这个区间其实就是每次进行搜索的区间。

    • while(left <= right) 的终止条件是 left == right + 1，写成区间的形式就是 [right + 1, right]，或者带个具体的数字进去 [3, 2]，可见这时候区间为空，因为没有数字既大于等于 3 又小于等于 2 的吧。所以这时候 while 循环终止是正确的，直接返回 -1 即可。
    • while(left < right) 的终止条件是 left == right，写成区间的形式就是 [right, right]，或者带个具体的数字进去 [2, 2]，这时候区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。
    • 所以当都是左闭右闭的时候，我们判断的条件是left<=right
    • 缺陷：比如说给你有序数组 nums = [1,2,2,2,3]，target 为 2，此算法返回的索引是 2，没错。但是如果我想得到 target 的左侧边界，即索引 1，或者我想得到 target 的右侧边界，即索引 3，这样的话此算法是无法处理

    寻找左侧边界的二分搜索

    1.  private int left_bound(int[] nums, int target) {
    2.         //找到这个数的最右边的边界
    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]
    8.                 left=mid+1;
    9.             }else if(nums[mid]>target){
    10.                 right=mid-1;
    11.             }else {
    12.                 right=mid-1;
    13.             }
    14.         }
    15.         //走到这里,说明left肯定大于right了
    16.         //一种情况,当这个值比数组的所有值都大,肯定会走到头left=length
    17.         //比如 1 2 2 2 3 找2
    18.         // left right mid
    19.         //  0     4    2
    20.         //  0     1    0
    21.         //  1     1    1
    22.         //  1     0
    23.         // 1 2 3 5 7 8
    24.         //  0     5     2
    25.         //  0     1     0
    26.         //  1     1     1
    27.         //  1     0
    28.         if (left>=nums.length||nums[left]!=target){
    29.             return -1;
    30.         }
    31.         return left;
    32.     }
    • 这里使用还是左闭右闭的区间[left,right]

    为什么该算法能够搜索左侧边界？

    答：关键在于对于 nums[mid] == target 这种情况的处理：

    1. if (nums[mid] == target) {
    2.             // 别返回，锁定左侧边界
    3.             right = mid - 1;
    4.         }
    • 可见，找到 target 时不要立即返回，而是缩小「搜索区间」的上界 right，在区间 [left, mid-1]中继续搜索，即不断向左收缩，达到锁定左侧边界的目的。

    寻找右侧边界的二分查找 

    1.  private int right_bound(int[] nums, int target) {
    2.         int left=0;
    3.         int right=nums.length-1;
    4.         while (left<=right){
    5.             int mid=left+(right-left);
    6.             if (nums[mid]>target){
    7.                 right=mid-1;
    8.             }else if (nums[mid]
    9.                 left=mid+1;
    10.             }else {
    11.                 left=mid+1;
    12.             }
    13.         }
    14.         // 1 2 2 2 3
    15.         // left  right mid
    16.         // 0      4     2
    17.         // 3      4     3
    18.         // 4      4     4
    19.         // 4      3
    20.         // 1 2 3 5 7 8
    21.         //  0     5     2
    22.         //  0     1     0
    23.         //  1     1     1
    24.         //  2     1
    25.         if (right<0||nums[right]!=target){
    26.             return -1;
    27.         }
    28.         return right;
    29.     }
    • 、这里的区间还是[left,right)

    为什么这个算法能够找到右侧边界？

    1. if (nums[mid] == target) {
    2.             // 别返回，锁定右侧边界
    3.             left = mid + 1;
    4.         }
    • 当 nums[mid] == target 时，不要立即返回，而是增大「搜索区间」的左边界 left，使得区间不断向右靠拢，达到锁定右侧边界的目的。

    为什么最后返回 left - 1 而不像左侧边界的函数，返回 left？而且我觉得这里既然是搜索右侧边界，应该返回 right 才对。

    答：首先，while 循环的终止条件是 left == right，所以 left 和 right 是一样的，你非要体现右侧的特点，返回 right - 1 好了。

    至于为什么要减一，这是搜索右侧边界的一个特殊点，关键在锁定右边界时的这个条件断：

    1. // 增大 left，锁定右侧边界
    2. if (nums[mid] == target) {
    3.     left = mid + 1;
    4.     // 这样想: mid = left - 1

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

    1. class Solution {
    2.      public int[] searchRange(int[] nums, int target) {
    3.         return new int[]{left_bound(nums,target),right_bound(nums,target)};
    4.     }
    5.  
    6.     private int left_bound(int[] nums, int target) {
    7.         //找到这个数的最右边的边界
    8.         int left=0;
    9.         int right=nums.length-1;
    10.         while (left<=right){
    11.             int mid=left+(right-left)/2;
    12.             if (nums[mid]
    13.                 left=mid+1;
    14.             }else if(nums[mid]>target){
    15.                 right=mid-1;
    16.             }else {
    17.                 right=mid-1;
    18.             }
    19.         }
    20.         //走到这里,说明left肯定大于right了
    21.         //一种情况,当这个值比数组的所有值都大,肯定会走到头left=length
    22.         //比如 1 2 2 2 3 找2
    23.         // left mid right
    24.         // 0     2     4
    25.         // 0     0      1
    26.         // 1     1      1
    27.         // 1     0      0
    28.         // 1 2 3 5 7 8
    29.         // 0     2      5
    30.         // 0     0       1
    31.         // 1     1       1
    32.         // 1     0       0
    33.         if (left>=nums.length||nums[left]!=target){
    34.             return -1;
    35.         }
    36.         return left;
    37.     }
    38.  
    39.     private int right_bound(int[] nums, int target) {
    40.         int left=0;
    41.         int right=nums.length-1;
    42.         while (left<=right){
    43.             int mid=left+(right-left);
    44.             if (nums[mid]>target){
    45.                 right=mid-1;
    46.             }else if (nums[mid]
    47.                 left=mid+1;
    48.             }else {
    49.                 left=mid+1;
    50.             }
    51.         }
    52.         // 1 2 2 2 3
    53.         // left mid right
    54.         // 0      2      4
    55.         // 3      3      4
    56.         // 4      4      4
    57.         // 4      3      3
    58.         if (right<0||nums[right]!=target){
    59.             return -1;
    60.         }
    61.         return right;
    62.     }
    63. }

    Offer 53

    1. class Solution {
    2.     public int search(int[] nums, int target) {
    3.         int left=left_bound(nums,target);
    4.         int right=right_bound(nums,target);
    5.         if (left==-1){
    6.             return 0;
    7.         }
    8.         return right-left+1;
    9.     }
    10.  
    11.  
    12.  
    13.     private int left_bound(int[] nums, int target) {
    14.         int left=0;
    15.         int right=nums.length-1;
    16.  
    17.         while (left<=right){
    18.             int mid=left+(right-left);
    19.             if (nums[mid]
    20.                 left=mid+1;
    21.             }else if (nums[mid]>target){
    22.                 right=mid-1;
    23.             }else {
    24.                 right=mid-1;
    25.             }
    26.         }
    27.         if (left==nums.length||nums[left]!=target){
    28.             return -1;
    29.         }
    30.         return left;
    31.     }
    32.  
    33.     private int right_bound(int[] nums, int target) {
    34.         int left=0;
    35.         int right=nums.length-1;
    36.         while (left<=right){
    37.             int mid=left+(right-left);
    38.             if (nums[mid]>target){
    39.                 right=mid-1;
    40.             }else if (nums[mid]
    41.                 left=mid+1;
    42.             }else {
    43.                 left=mid+1;
    44.             }
    45.         }
    46.         if (right<0||nums[right]!=target){
    47.             return -1;
    48.         }
    49.         return right;
    50.     }
    51. }

    Offer04 

    • 从右上角开始找，如果大于就往一行的左边找，如果小于就往一列的下面找

    1. class Solution {
    2.     public boolean findNumberIn2DArray(int[][] matrix, int target) {
    3.             if (matrix==null||matrix.length==0){
    4.                 return false;
    5.             }
    6.             return helper(matrix,target,0,matrix[0].length-1);
    7.     }
    8.  
    9.     private boolean helper(int[][] matrix, int target, int row, int column) {
    10.         if (row<0||row>=matrix.length||column<0||column>=matrix[0].length){
    11.              return false;
    12.         }else if (matrix[row][column]==target){
    13.             return true;
    14.         }else if (matrix[row][column]>target){
    15.             return helper(matrix,target,row,column-1);
    16.         }else {
    17.             return helper(matrix,target,row+1,column);
    18.         }
    19.     }
    20. }
    1. class Solution {
    2.     public boolean searchMatrix(int[][] matrix, int target) {
    3.         int m = matrix.length, n = matrix[0].length;
    4.         // 初始化在右上角
    5.         int i = 0, j = n - 1;
    6.         while (i < m && j >= 0) {
    7.             if (matrix[i][j] == target) {
    8.                 return true;
    9.             }
    10.             if (matrix[i][j] < target) {
    11.                 // 需要大一点，往下移动
    12.                 i++;
    13.             } else {
    14.                 // 需要小一点，往左移动
    15.                 j--;
    16.             }
    17.         }
    18.         // while 循环中没有找到，则 target 不存在
    19.         return false;
    20.     }
    21. }

    Offer 11旋转数组的最小数字

    1. class Solution {
    2.          public int minArray(int[] numbers) {
    3.         int n=numbers.length-1;
    4.         int left=0;
    5.         int right=n;
    6.         while (left
    7.             int mid=left+(right-left)/2;
    8.             if (numbers[mid]>numbers[right]){
    9.                 //说明mid在左区间
    10.                 left=mid+1;
    11.             }else if(numbers[mid]
    12.                 //说明mid现在在右区间
    13.                 right=mid;
    14.             }else {
    15.                 //当值相同的时候,我们不能判读在那个区间,因为
    16.                 //1 1 2 3 4 ->1 2 3 4 1
    17.                 //1 1 2 3 4 ->2 3 4 1 1
    18.                 right=right-1;
    19.                 //当确定不了的时候 我们就减少右边的范围,因为左边还存在相同的这个值
    20.             }
    21.         }
    22.         return numbers[left];
    23.     }
    24. }

    Offer 53 II

    1. class Solution {
    2.       public int missingNumber(int[] nums) {
    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]==mid){
    8.                 //说明mid之前都没问题
    9.                 left=mid+1;
    10.             }else if (nums[mid]!=mid){
    11.                 //说明mid之前有问题
    12.                 right=mid-1;
    13.             }
    14.         }
    15.         return left;
    16.     }
    17.  
    18. }

    33搜索旋转排序数组

     

    • 对于有序的序列或者部分有序的序列都可以使用二分，或者二分的变种，这里我们知道前面的数组是升序的，后面数组也是有序的，但是后面的数组的最大值小于前面数组的最小值，我们就利用这个特性，找到一个mid，看是否跟找的值一样大，

     

     

    1. class Solution {
    2.        public int search(int[] nums, int target) {
    3.             int n=nums.length-1;
    4.             int left=0;
    5.             int right=nums.length-1;
    6.             while (left<=right){
    7.                 int mid=left+(right-left)/2;
    8.                 if (nums[mid]==target){
    9.                     return mid;
    10.                 }else if (nums[mid]
    11.                     //说明后半段是有序的
    12.                     if (target<=nums[right]&&target>nums[mid]){
    13.                         //说明这个数是处于后面的有序数组的
    14.                         left=mid+1;
    15.                     }else {
    16.                         //要么target>nums[right] //说明可能存在前面的序列 
    17.                         //要么target
    18.                         //mid是2 但是我们找到是1
    19.                         right=mid-1;
    20.                     }
    21.                 }else {
    22.                     //说明前半段是有序的
    23.                     if (target>nums[right]&&target
    24.                         //说明target可能存在在前面的有序队列
    25.                         right=mid-1;
    26.                     }else {
    27.                         //要么target小于nums[right] //可能存在于后面的序列
    28.                         //要么target大于nums[mid] 在后面也可能存在   4 5 6 7 8 1 2
    29.                         //找 8 mid是7 8在mid后面
    30.                         left=mid+1;
    31.                     }
    32.                 }
    33.             }
    34.             return -1;
    35.     }
    36.  
    37. }

    287寻找重复数

     

    1. class Solution {
    2.         public int findDuplicate(int[] nums) {
    3.         //二分法+抽屉定理
    4.         //如果n+1个物品放到n个盒子里，必定有一个盒子的要装两个物品
    5.         //因为数的取值范围是[0,n],我们找一个数，统计比它小的数出现过多少次，
    6.         //如果出现的次数大于了这个数(这个数是盒子的数量,比他小的数出现的个数是物品的数量)
    7.         //说明那个出现过多次的数肯定是比这个数小,我们就可以利用二分法来缩小范围
    8.         int left=0;
    9.         int right=nums.length-1;
    10.         int count;
    11.         while (left
    12.             count=0;
    13.             int mid=left+(right-left)/2;
    14.             for (int i:nums) {
    15.                 if (i<=mid){
    16.                     count++;
    17.                 }
    18.             }
    19.             if (count>mid){
    20.                 right=mid;
    21.             }else {
    22.                 left=mid+1;
    23.             }
    24.         }
    25.         return left;
    26.     }
    27.  
    28. }
    •  这里二分的是数组取值的范围，并不是说这个数组的值的范围

    快慢指针法

     

    1.    public int findDuplicate(int[] nums) {
    2.             int slow=0;
    3.             int fast=0;
    4.             slow=nums[0];
    5.             fast=nums[nums[0]];
    6.             while (slow!=fast){
    7.                 slow=nums[slow];
    8.                 fast=nums[nums[fast]];
    9.             }
    10.             fast=slow;
    11.             slow=0;
    12.             while (slow!=fast){
    13.                 slow=nums[slow];
    14.                 fast=nums[fast];
    15.             }
    16.             return slow;
    17.     }
    • 因为下标是唯一的，但是可能对应的值不是唯一的，所以当用下标去找值的时候，如果有一个值是重复的，我们索引对应着一个值，当这个值第一次出现时候，它就会作为一个索引来对应一个值，当这个值又作为值出现，那么就会找到刚刚出现的那个值，形成循环
  • 相关阅读:
    nodejs+vue 校园通勤车-计算机毕业设计
    如何在 Docker 容器中运行 MySQL
    了解 OpenJDK 以及为什么要使用OpenJDK？
    react context
    堆栈认知——栈溢出实例（ret2libc）
    Team Finance被黑分析｜黑客自建Token“瞒天过海”，成功套取1450万美元
    CSDN第11次竞赛题解与总结
    spring-cloud-starter-dubbo不设置心跳间隔导致生产者重启no Provider问题记录
    Spring依赖注入
    Yii实现RabbitMQ队列
  • 原文地址：https://blog.csdn.net/qq_50985215/article/details/126233512