LeetCode分类专题（三）—

iwehdio的博客园：https://www.cnblogs.com/iwehdio/

学习自：

二分查找算法详解
如何运用二分查找算法
一文带你搞定多个二分查找变种题目
本文包括LeetCode：29、33、34、35、69、50、74、81、153

1、二分搜索

二分搜索
- 首先，二分搜索的思想是，每次减少问题的一半规模。对于有序数组而言，是通过每次比较mid的值与目标值的大小而定的。
- 根据右边界是闭区间还是开区间，可以分为两种。区别在于：
  1. 右边界的初始值是length还是length-1。
  2. 结束条件是left < right还是left <= right。
  3. 改变右边界时是right = mid还是right = mid - 1。
  4. 一般来说，选取闭区间的程序可读性较好，所以一般选第二种。
- 查找有序数组中的元素：

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


//-----------------------------------------


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

对于右边界为length-1的情况而言：
1. left/right左右边界对应的就是最左和最右元素的索引。
1. nums[mid] < target就意味着mid的左侧都比target小，那么target可能落在 [mid,hi]，但是mid如果单独判断过的话，就是[mid+1,hi]，所以left赋值为mid+1，即left左侧（不包含）都比target小。
2. 相应的，right右侧（不包含）都比target大，所以right赋值为mid-1。
3. 结束条件是left <= right。这意味着，最后一次循环时，left与right是重合的。此时，只需要判断这个重合的位置mid是否等于target。如果等于就找到返回。
4. 如果不等于，就应该返回插入位置。插入位置的含义是，数组中大于target的最小值。
- 如果mid小于target，说明left应该右移一位，插入位置在left。
- 如果mid大于target，说明right应该左移一位，插入位置还是在left。
查找有序数组中的元素并返回插入位置：

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

如果数组中存在重复元素，那么目标就成了搜索重复元素的最左或最右端元素。如果是找做边界，在这种情况下，left的含义还是左侧（不包含）都比target小，而right的含义变为了right右侧（不包含）都大于等于target，此时target=mid的情况归入right。
因此，最后的情况就是，最后一次循环中，重合的mid要么是target的左边界，要么是左边界的往左一个元素。因为只有这两种情况才能同时符合left和right的定义。
计算左右边界，二者唯一的区别就是等号被归入了不同的情况：

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

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

2、旋转数组

旋转数组
- 旋转数组，是由有序数组从一个点旋转而来的，也可以用二分查找来查找元素。原因是，二分查找只是要求每次减少一半规模，如果不是完全有序的话，不能只根据mid与target的大小关系，需要借助其他条件。
- 根据二分的思想，应该得出target在mid的左侧或者右侧。在无重复元素的情况下：
  - 如果mid大于left，那么mid左侧是有序的，可以得出：
    - 如果left<target<mid，那么target在mid左侧，否则在右侧。
  - 如果mid小于left，那么mid右侧是有序的，同样可以得出：
    - 如果mid<target<right，那么target在mid右侧，否则在左侧。

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

如果旋转数组中有重复元素的话，就可能出现mid与left相等的情况，这样就没法判断是左边有序还是右边有序了，需要移动左边界一直到左边界与mid不等。

class Solution {
    public boolean search(int[] nums, int target) {
        int lo=0, hi = nums.length-1;
        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(nums[mid]==target) {
                return true;
            }
            if(nums[mid]==nums[lo]) {
                lo++;
                continue;
            }
            if(nums[mid]<nums[lo]) {
                if(target>nums[mid] && target<=nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            } else {
                if(target<nums[mid] && target>=nums[lo]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
        }
        return false;
    }
}

查找旋转数组中的最小值，这种情况下延续之前的思想，比较mid与left：
- 如果mid小于left，则[mid,right]是有序的，最小值可能在[left,mid]中。
- 如果mid大于等于left，则[left,mid]是有序的，最小值可能在[mid+1,right]中。
- 需要注意的是退化情况，即如果数组是有序的，直接返回left。这通过比较left和right来决定。
为什么left=mid+1，而right=mid？
- 因为mid右侧有序，那么mid本身可能是最小值，但是如果mid左侧有序，那么mid必定不是最小值。
为什么=mid的情况归到了left？
- 因为如果出现=的情况，一定是区间只存在left/mid和right两个元素，而又没有left<right自然有序，最小值就是right了。

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

3、题目

29 两数相除

这个题的如果使用一次次减来等效乘法，时间复杂度太高了，所以需要倍数递增。
比如19/6，19比6大，然后6倍增为12；19比12大，然后12倍增为24；19比24小，则19/6的商为：倍数2 + （19-12）/6。递归的执行。
所以，这里div函数的含义是，计算出x<y*2^n中n的最大值（x、y为负数）。
这里比较坑的是，需要考虑int类型的溢出问题。数值为-2^31~231-1，也就是说，整数比负数少一个，因此可以全部转为负数来规避溢出。
此外，在倍增过程中，如果当前的减数大于Integer.MIN_VALUE=-2^31，也不能再递增了，否则就会溢出。而最后的结果，如果是Integer.MIN_VALUE，则其相反数会溢出，需要返回Integer.MAX_VALUE。
溢出的结果是Integer.MAX_VALUE+1=，Integer.MIN_VALUE-1=Integer.MAX_VALUE。

class Solution {

    int ans = 0;
    public int divide(int dividend, int divisor) {
        //全部转为负数
        boolean flag = false;
        if((dividend<0 && divisor>0)||(dividend>0 && divisor<0)) {
            flag = true;
        }
        if(dividend>0) dividend = -dividend;
        if(divisor>0) divisor = -divisor;
        //递归除法
        while(dividend <= divisor) {
            dividend = div(dividend, divisor);
        }
        //根据flag复原结果
        if(flag) {
            return -ans;
        } else {
            //如果溢出
            if(ans == Integer.MIN_VALUE) return Integer.MAX_VALUE;
            return ans;
        }
    }
	//倍增除法
    public int div(int x, int y) {
        int res = 1;
        while(x <= (y << 1)){
            if(y <= (Integer.MIN_VALUE >> 1)) break;
            y <<= 1;
            res <<= 1;
        }
        ans += res;
        return x - y;
    }
}

33 搜索旋转排序数组

二分查找的本质甚至不是有序，而是每次减半规模，也就是分治。在这种情况下，每次减少一半的问题规模，就是看目标元素是在中间元素的左边还是右边。
具体的来说，是跟边界元素、中间元素和目标元素的大小关系有关。
如果中间元素大于等于左边界元素：
- 如果左边界元素<=目标元素<中间元素，则目标元素在中间元素的左侧。
- 否则，在右侧。
如果中间元素小于左边界元素：
- 如果中间元素<目标元素<=右边界元素，则目标元素在中间元素的右侧。
- 否则，在左侧。

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

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

首先用一个二分查找找到目标元素，然后再用两个二分查找搜索左右边界。
对于返回值，二分搜索最后一定是hi在lo左侧终止，即hi+1=lo。
- findleft，lo的含义是小于target的都在lo左侧，而大于等于target的都在hi右侧，因此左边界是lo。
- findright，小于等于target的都在lo左侧，大于hi的都在hi右侧，因此返回hi。

class Solution {

    int left = -1;
    int right = -1;

    public int[] searchRange(int[] nums, int target) {
        int lo = 0, hi = nums.length-1;
        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(nums[mid]==target) {
                findleft(nums, target, lo, hi);
                findright(nums, target, lo, hi);
                break;
            } else if(nums[mid]>target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        } 
        return new int[]{left,right};
    }

    public void findleft(int[] nums, int target, int lo, int hi) {
        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(nums[mid]>=target) {
                hi = mid - 1;
            } else if(nums[mid]<target) {
                lo = mid + 1;
            }
        }
        left = lo;
    }

    public void findright(int[] nums, int target, int lo, int hi) {
        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(nums[mid]<=target) {
                lo = mid + 1;
            } else if(nums[mid]>target) {
                hi = mid - 1;
            }
        }
        right = hi;
    }
}

35 搜索插入位置

二分查找，重要的是找不到的情况下的返回值。初始值hi设置为数组长度，避免了单独处理大于数组中所有数的问题。
最后当区间长度为1时，如果目标元素小于则就在mid处插入，否则在mid+1处。

class Solution {
    public int searchInsert(int[] nums, int target) {
        int lo = 0, hi = nums.length-1;
        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(nums[mid]==target) {
                return mid;
            } else if(nums[mid]>target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
}

69 x的平方根
- 二分查找[0,x]区间内的值。坑的点主要有2：
  - 输入的最大值为int的上限，此时mid*mid可能会溢出，需要转换为long。
  - x的平方根可能为x自己，所以搜索应包含x。如果以lo<hi为终止条件，即区间右边界为不包含，起始值hi应为x+1，可能会溢出。所以需要以lo<=hi为终止条件，起始值为x。
- 因为去掉小数部分，即平方小于x，返回值为lo-1，即小于平方根的最大整数。
```
class Solution {
    public int mySqrt(int x) {
        int lo=0, hi = x;
        while(lo<=hi) {
            int mid = lo + (hi-lo)/2;
            if((long)mid*mid==x) {
                return mid;
            }
            if(x<(long)mid*mid) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return lo-1;
    }
}
```

50 Pow(x，n)

本题的问题仍然是负数最大值大于正数，所以转换时要改为long。

class Solution {
    public double myPow(double x, int n) {
        boolean isNeg = false;
        long N = (long)n;
        if(N<0) {
            isNeg = true;
            N = -N;
        }
        double ans = 1;
        while(N>0) {
            if((N&1)==1) {
                ans *= x;
            }
            N >>= 1;
            x *= x;
        }
        if(isNeg) {
            return 1/ans;
        } else {
            return ans;
        }
    }
}

74 搜索二维矩阵

先用一个二分搜索找出所在的行，即小于等于目标元素的最大值，返回lo-1/hi。
这里需要校验lo-1的合法性，因为可能目标元素小于第一行的最小值，这样就直接返回false了。
然后再用一个普通的二分查找找出所在的列。

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int mlo=0, mhi=matrix.length-1;
        while(mlo<=mhi) {
            int mmid = (mlo+mhi)/2;
            if(target<matrix[mmid][0]) {
                mhi = mmid - 1;
            } else {
                mlo = mmid + 1;
            }
        }
        int index = mhi;
        if(index<0) return false;
        int lo=0, hi=matrix[index].length-1;
        while(lo<=hi){
            int mid = (lo+hi)/2;
            if(target==matrix[index][mid]) {
                return true;
            }
            if(target<matrix[index][mid]) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return false;
    }
}

81 搜索旋转排序数组Ⅱ

与之前的旋转数组不同的地方主要在于，可能会出现重复元素。
出现重复元素，可能会导致无法根据左边界和 mid的大小关系判断旋转点在mid的哪一边（比如数组[1,0,1,1,1]），需要逐个缩减边界。
需要注意的是target和左边界或者右边界比较时，需要加=号。

class Solution {
    public boolean search(int[] nums, int target) {
        int lo=0, hi = nums.length-1;
        while(lo<=hi) {
            int mid = (lo+hi)/2;
            if(nums[mid]==target) {
                return true;
            }
            if(nums[mid]==nums[lo]) {
                lo++;
                continue;
            }
            if(nums[mid]<nums[lo]) {
                if(target>nums[mid] && target<=nums[hi]) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            } else {
                if(target<nums[mid] && target>=nums[lo]) {
                    hi = mid - 1;
                } else {
                    lo = mid + 1;
                }
            }
        }
        return false;
    }
}

153 寻找旋转排序数组中的最小值
- 首先看数组是不是有序的（通过比较左边界和右边界的大小），如果是有序的，就返回左边界。
- 否则，看mid与左边界（nums[mid]>=nums[lo]）或右边界（nums[mid]<nums[hi]）的大小关系，减少一半规模。

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

iwehdio的博客园：https://www.cnblogs.com/iwehdio/

转载请注明出处:http://www.btxqwz.com/article/20230319/563998.html

随机推荐

[LeetCode] 923. 3Sum With Multiplicity 三数之和的多种情况
Given an integer array`A`, and an integer`target`, return the number oftuples`i, j, k` such that`i j k`and`A[i] + A[...
LeetCode分类专题（三）——二分查找1
iwehdio的博客园：https://www.cnblogs.com/iwehdio/ 学习自：二分查找算法详解如何运用二分查找算法一文带你搞定多个二分查找变种题目本文包括LeetCode：29、33、34、35...
LeetCode - 最接近的三数之和
最接近的三数之和你一个长度为 n 的整数数组nums和一个目标值target。请你从 nums 中选出三个整数，使它们的和与target最接近。返回这三个数的和。假定每组输入只存在恰好一个解。示例 1：输入：nums = [-...
LeetCode-16. 最接近的三数之和
题目来源最接近的三数之和题目详情给你一个长度为 n 的整数数组nums和一个目标值target。请你从 nums 中选出三个整数，使它们的和与target最接近。返回这三个数的和。假定每组输入只存在恰好一个解。示例 1： ...
[LeetCode] 1. Two Sum 两数之和
Given an array of integers, returnindicesof the two numbers such that they add up to a specific target. You may assume...
Leetcode 240. 搜索二维矩阵 II 暴力与二分
地址 https://leetcode-cn.com/problems/search-a-2d-matrix-ii/ 编写一个高效的算法来搜索mxn矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：每行的元素从左...
LeetCode——分类颜色
Q：给定一个包含红色、白色和蓝色，一共n个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排序。此题中，我们使用整数0、1和2分别表示红色、白色和蓝色。【示例】输入：[2, 0, 2, 1, 1, ...
LeetCode 977. 有序数组的平方双指针二分
地址https://leetcode-cn.com/problems/squares-of-a-sorted-array/ 给定一个按非递减顺序排序的整数数组 A，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。示例 1...
[LeetCode] 191. Number of 1 Bits 二进制数1的个数
Write a function that takes an unsigned integer and returns the number of ’1' bits it has (also known as theHamming wei...
LeetCode 75 Sort Colors 颜色分类
描述 Given an array nums with n objects colored red, white, or blue, sort them in-place so that objects of the same color...

包头市兴启物资有限责任公司

LeetCode分类专题（三）——二分查找1

1、二分搜索

2、旋转数组

3、题目

随机推荐

相关专题