二分题目总结

刺骨的言语ヽ痛彻心扉 2022-02-15 05:23 183阅读 0赞

## 1. 二分模板 ##

1.  当我们将区间\[l, r\]划分成\[l, mid\]和\[mid + 1, r\]时，其更新操作是r = mid或者l = mid + 1;，计算mid时不需要加1。

int bsearch_1(int l, int r)
    {
        
        while (l < r)
        {
        
            int mid = l + r >> 1;
            if (check(mid)) r = mid;
            else l = mid + 1;
        }
        return l;
    }

1.  当我们将区间\[l, r\]划分成\[l, mid - 1\]和\[mid, r\]时，其更新操作是r = mid - 1或者l = mid;，此时为了防止死循环，计算mid时需要加1。

int bsearch_2(int l, int r)
    {
        
        while (l < r)
        {
        
            int mid = l + r + 1 >> 1;
            if (check(mid)) l = mid;
            else r = mid - 1;
        }
        return l;
    }

## 2. Sqrt(x) ##

**原题链接：**  
[https://leetcode.com/problems/sqrtx/][https_leetcode.com_problems_sqrtx]  
**题目描述：**  
Implement int sqrt(int x).  
Compute and return the square root of x, where x is guaranteed to be a non-negative integer.  
Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

样例输入1:  
Input: 4  
Output: 2

样例输入 2:  
Input: 8  
Output: 2  
Explanation: The square root of 8 is 2.82842…, and since  
the decimal part is truncated, 2 is returned.

**思路：**  
普通的二分问题，二分x，直到找到答案，需要注意的是边界问题，题目要求是向下取整，注意边界的更新。

**代码：**

class Solution {
        
    public:
        int mySqrt(int x) {
        
            int l = 0, r = x;
            while(l < r)
            {
        
                int mid = (l + r + 1ll) >> 1;
                if(mid * 1ll * mid <= x) l = mid; // 注意数的范围有可能超过int的最大值， 使用1ll强制转化为long long
                else r = mid - 1;
            }
            return l;
        }
    };

## 3. Find First and Last Position of Element in Sorted Array ##

**原题链接：**  
[https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/][https_leetcode.com_problems_find-first-and-last-position-of-element-in-sorted-array]  
**题目描述：**  
Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.  
Your algorithm’s runtime complexity must be in the order of O(log n).  
If the target is not found in the array, return \[-1, -1\].

样例输入 1:  
Input: nums = \[5,7,7,8,8,10\], target = 8  
Output: \[3,4\]

样例输入 2:  
Input: nums = \[5,7,7,8,8,10\], target = 6  
Output: \[-1,-1\]

**思路：**  
这个题目就充分的考验了上一题中说的边界问题，通过对l， r的更新的不同，来找到答案的上边界和下边界。

**代码：**

class Solution {
        
    public:
        vector<int> searchRange(vector<int>& nums, int target) {
        
            if(!nums.size())
                return {
        -1, -1};
            vector<int> res;
            int l = 0, r = nums.size() - 1, mid;
            while(l < r)
            {
        
                int mid = (l + r) >> 1;
                if(nums[mid] >= target) r = mid;
                else l = mid + 1;
            }
            if(nums[l] == target) res.push_back(l);
            else return {
        -1, -1};
            
            l = 0, r = nums.size() - 1;
            while(l < r)
            {
        
                int mid = (l + r + 1) >> 1;
                if(nums[mid] <= target) l = mid;
                else r = mid - 1;
            }
            if(nums[r] == target) res.push_back(r);
            else res.push_back(-1);
            return res;
        }
    };

## 4.Search a 2D Matrix ##

**原题链接：**  
[https://leetcode.com/problems/search-a-2d-matrix/][https_leetcode.com_problems_search-a-2d-matrix]  
**题目描述：**  
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:  
Integers in each row are sorted from left to right.  
The first integer of each row is greater than the last integer of the previous row.

样例输入 1:  
Input:  
matrix = \[  
\[1, 3, 5, 7\],  
\[10, 11, 16, 20\],  
\[23, 30, 34, 50\]  
\]  
target = 3  
Output: true

样例输入 2:  
Input:  
matrix = \[  
\[1, 3, 5, 7\],  
\[10, 11, 16, 20\],  
\[23, 30, 34, 50\]  
\]  
target = 13  
Output: false

**思路：**  
题目中的矩阵是有序的，所有我们只需要把二维的矩阵转化为一维的数组即可。把二维矩阵看作一维数组的话，这个一维数组的长度就是 【n(矩阵的行数) \* m(矩阵的列数)】,那么这个一维数组的第k个元素对应二维矩阵的第 k/m 行，第 k%m 列的元素。

**代码：**

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

## 5.Search a 2D Matrix II ##

**原题链接：**  
[https://leetcode.com/problems/search-a-2d-matrix-ii/][https_leetcode.com_problems_search-a-2d-matrix-ii]  
**题目描述：**  
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:  
Integers in each row are sorted in ascending from left to right.  
Integers in each column are sorted in ascending from top to bottom.

Example:  
Consider the following matrix:

\[  
\[1, 4, 7, 11, 15\],  
\[2, 5, 8, 12, 19\],  
\[3, 6, 9, 16, 22\],  
\[10, 13, 14, 17, 24\],  
\[18, 21, 23, 26, 30\]  
\]  
Given target = 5, return true.  
Given target = 20, return false.

**思路：**  
和上一题不同的是，本题的矩阵只保证每一行从左到右递增，每一列从左到右递增，不保证整体的递增。这个题的关键点在右上角的那一点，我们从右上角的点进行分析，如果：  
**1. 右上角的值等于目标值，就找到答案了，直接返回。  
2. 右上角的值 < 目标值，那么目标值一定是出现在该值的下方，不可能出现在左边。  
3. 右上角的值 > 目标值，那么目标值一定是出现在该值的左边，不可能出现在下方。**  
这样通过分析我们可以发现，每一次我们可以去除一行或者一列，在O(n + m)的时间内就可以找到目标值。

**代码：**

class Solution {
        
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
        
            if(!matrix.size() || !matrix[0].size())
                return false;
            int n = matrix.size(), m = matrix[0].size();
            int bx = m - 1, by = 0;
            while(bx >= 0 && by < n)
            {
        
                int t = matrix[by][bx];
                if(t == target)
                    return true;
                else if(t < target)
                    by++;
                else
                    bx--;
                
            }
            return false;
        }
    };

## 6.Find Minimum in Rotated Sorted Array ##

**原题链接：**  
[https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/][https_leetcode.com_problems_find-minimum-in-rotated-sorted-array]  
**题目描述：**  
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.  
(i.e., \[0,1,2,4,5,6,7\] might become \[4,5,6,7,0,1,2\]).  
Find the minimum element.  
You may assume no duplicate exists in the array.

样例输入 1:  
Input: \[3,4,5,1,2\]  
Output: 1

样例输入 2:  
Input: \[4,5,6,7,0,1,2\]  
Output: 0

**思路：**  
假设数组为nums  
当没有经过交换， 即nums.front() < nums.back(), 那么最小值就是nums.front()  
否则，  
我们不难看出最小值的特征，虽然经过的交换，但是最小值的特征没变， 分析一波：  
1. 当 nums\[mid\] >= nums\[0\]时，那么最小值一定出现 mid的右边，不包含mid  
2. 当 nums\[mid\] < nums\[0\]时，那么最小值一定出现在mid的左边，包含mid  
**代码：**

class Solution {
        
    public:
        int findMin(vector<int>& nums) {
        
            if(nums.empty())
                return -1;
            if(nums[0] < nums.back())
                return nums[0];
            int l = 0, r = nums.size() - 1;
            while(l < r)
            {
        
                int mid = l + r >> 1;
                if(nums[mid] >= nums[0]) l = mid + 1;
                else r = mid;
            }
            
            return nums[r];
        }
    };

## 7.Find Peak Element ##

**原题链接：**  
[https://leetcode.com/problems/find-peak-element/][https_leetcode.com_problems_find-peak-element]  
**题目描述：**  
A peak element is an element that is greater than its neighbors.  
Given an input array nums, where nums\[i\] ≠ nums\[i+1\], find a peak element and return its index.  
The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.  
You may imagine that nums\[-1\] = nums\[n\] = -∞.

样例输入 1:  
Input: nums = \[1,2,3,1\]  
Output: 2  
Explanation: 3 is a peak element and your function should return the index number 2.

样例输入 2:  
Input: nums = \[1,2,1,3,5,6,4\]  
Output: 1 or 5  
Explanation: Your function can return either index number 1 where the peak element is 2,  
or index number 5 where the peak element is 6.

**思路：**  
注意题目中，nums\[-1\] 和 nums\[n\]为 负无穷， 所以边界点只需要满足另一边小于自身即可。  
那nums\[mid\] 和 nums\[mid+1\] 作比较：  
1. **当 nums\[mid\] < nums\[mid + 1\] 时, 那么在mid的右边一定会出现峰值，为什么呢？我们假设不出现峰值，那么，mid右边的序列一定时单调并且递增的。如果他是单调递增的，因为nums\[n\]是负无穷，所以右端点就是峰值了，所以当 nums\[mid\] < nums\[mid + 1\] 时， 右边一定存在峰值。**  
2. 当 nums\[mid\] > nums\[mid + 1\] 时， 同理。  
这样就可以每次把区间缩小一半。

**代码：**

class Solution {
        
    public:
        int findPeakElement(vector<int>& nums) {
        
            if(nums.empty())
                return -1;   
            int l = 0, r = nums.size() - 1;
            while(l < r)
            {
        
                int mid = l + r >> 1;
                if(mid == nums.size() - 1) // 特判一波区间端点
                    return mid;
                else if(nums[mid] < nums[mid + 1]) l = mid + 1;
                else r = mid;
            }
            
            return r;
        }
    };

[https_leetcode.com_problems_sqrtx]: https://leetcode.com/problems/sqrtx/
[https_leetcode.com_problems_find-first-and-last-position-of-element-in-sorted-array]: https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
[https_leetcode.com_problems_search-a-2d-matrix]: https://leetcode.com/problems/search-a-2d-matrix/
[https_leetcode.com_problems_search-a-2d-matrix-ii]: https://leetcode.com/problems/search-a-2d-matrix-ii/
[https_leetcode.com_problems_find-minimum-in-rotated-sorted-array]: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
[https_leetcode.com_problems_find-peak-element]: https://leetcode.com/problems/find-peak-element/