Leetcode中的二分题目

我就是我 2022-07-14 04:18 118阅读 0赞

这一次的二分姿势都是学习上一篇文章的。

[Leetcode 33. Search in Rotated Sorted Array][]  
一个不是标准递增的序列  
那么你就要先找到那个分界点。

第一想法是，与target比大小得到分界点。但是会出现一些问题，因为有可能target比所有序列数都大（或者都小），就会出现问题。于是只能用序列内的数作为标杆。  
第二想法就是，得到了分界点之后，分两段开始二分。这样也行，但是太麻烦了。于是发现分界点也是一个类似于循环节点的东西。所以通过取模进行平移，简化代码。

最后注意的是，通过平移得到的位置，在输出答案的时候要记得平移回去。我就是没有平移回去错了好几次。

class Solution(object):
        def search(self, nums, target):
            """ :type nums: List[int] :type target: int :rtype: int """
            n = len(nums)
            l = -1
            r = n - 1
    
            while l + 1 < r:
                mid = l + (r - l >> 1)
                if nums[mid] > nums[r]:
                    l = mid
                else:
                    r = mid
    
            half = r
    
            l = 0
            r = n
            while l + 1 < r:
                mid = l + (r - l >> 1)
                realmid = (mid + half) % n
                if nums[realmid] > target:
                    r = mid
                else:
                    l = mid
    
            if nums[(l+half)%n] == target:
                return (l+half)%n
            else:
                return -1

[Leetcode 34. Search for a Range][]

下限是lower\_bound  
上限是upper\_bound-1  
感觉这里左闭右开，左开右闭都行。  
只是一个是区间下限，一个是区间上限，所以我就用各自能够取到的位置去求。

class Solution(object):
        def searchRange(self, nums, target):
            """ :type nums: List[int] :type target: int :rtype: List[int] """
            l = -1
            r = len(nums) - 1
            ans = [0, 0]
            while l+1 < r:
                mid = l + (r - l >> 1)
                if nums[mid] >= target:
                    r = mid
                else:
                    l = mid
            if nums[r]!= target:
                ans[0] = -1
            else:
                ans[0] = r
    
            l = 0
            r = len(nums)
            while l+1 < r:
                mid = l + (r - l >> 1)
                if nums[mid] <= target:
                    l = mid
                else:
                    r = mid
    
            if nums[l]!= target:
                ans[1] = -1
            else:
                ans[1] = l
            return ans

[Leetcode 35. Search Insert Position][]  
找到最小的大于等于target的值的位置  
要用左开右闭，judge是递增性质的（越大的数，越可能是大于target的值）。  
当然，也可以认为这样更加方便地得到大于target的位置。

class Solution(object):
        def searchInsert(self, nums, target):
            """ :type nums: List[int] :type target: int :rtype: int """
            l = -1
            r = len(nums)
    
            while l+1 < r:
                mid = l + (r - l >> 1)
                if nums[mid] < target:
                    l = mid
                else:
                    r = mid
    
            return r

[Leetcode 69. Sqrt(x)][Leetcode 69. Sqrt_x]  
用的是左闭右开  
用左开右闭没有成功，不过应该是有一些不太好看的姿势可以过的吧。

class Solution(object):
        def mySqrt(self, x):
            """ :type x: int :rtype: int """
            if x == 0 or x == 1:
                return x
            l,r = 0, x/2+1
            while l+1<r:
                mid = l + ((r - l) >> 1)
                if mid**2 <= x:
                    l = mid
                else:
                    r = mid
            return l

[Leetcode 74. Search a 2D Matrix][]

这题最关键的问题是mid = (l+r)/2上下取整的问题。  
如果是下取整，会出现死循环或者答案不对的情况，我不太明白为什么会出现这个问题。但是确实是会发生。  
第一个二分，我们要求的是小于val的最大值。

> 假设区间为\[l,r\]，中间值为mid。  
> 如果num\[mid\] > val  
> 则区间变成\[l,mid-1\]  
> 否则变成\[mid,r\]  
> 因此，如果采用下取整的方式，r-l<=1的时候，l不变，为避免这种情况，则采用上取整。

class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            if(matrix.empty())  return false;
    
            int n = matrix.size(); //行数
            int m = matrix[0].size();//列数
    
            if(matrix[0][0] > target || matrix[n-1][m-1] < target)  return false;
            int l = 0, r = n - 1;
            while(l <= r)
            {
                int mid = l + (r - l + 1 >> 1);
                if(matrix[mid][0] > target) r = mid - 1;
                else if(matrix[mid][0] < target) l = mid + 1;
                else return true;
            }
            int row = r; 
            l = 0, r = m - 1;
            while(l <= r)
            {
                int mid = l + (r - l >> 1);
                if(matrix[row][mid] > target) r = mid - 1;
                else if(matrix[row][mid] < target) l = mid + 1;
                else return true;
            }
            return false;
        }
    };

[Leetcode 33. Search in Rotated Sorted Array]: https://leetcode.com/problems/search-in-rotated-sorted-array/
[Leetcode 34. Search for a Range]: https://leetcode.com/problems/search-for-a-range/
[Leetcode 35. Search Insert Position]: https://leetcode.com/problems/search-insert-position/
[Leetcode 69. Sqrt_x]: https://leetcode.com/problems/sqrtx/
[Leetcode 74. Search a 2D Matrix]: http://oj.leetcode.com/problems/search-a-2d-matrix/