LeetCode 8题 --Array+Binary search**

妖狐艹你老母 2022-08-05 13:13 69阅读 0赞

这5道题都是array的binary search就可以搞定了

分别是leetcode(35)——[Search Insert Position][] leetcode(34)——[Search for a Range][] leetcode(74)——[Search a 2D Matrix][] LeetCode(153)[Find Minimum in Rotated Sorted Array][] LeetCode(154)[Find Minimum in Rotated Sorted Array II][] leetcode(33)——[Search in Rotated Sorted Array][] leetcode(81)——[Search in Rotated Sorted Array II][] LeetCode(162) [Find Peak Element][]

**一：leetcode(35)——[Search Insert Position][]**

题目：

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You may assume no duplicates in the array.

Here are few examples.  
`[1,3,5,6]`, 5 → 2  
`[1,3,5,6]`, 2 → 1  
`[1,3,5,6]`, 7 → 4  
`[1,3,5,6]`, 0 → 0

链接：https://leetcode.com/problems/search-insert-position/

分析：通过分析我们发现当找到直接返回mid就可以了，当没找到需要返回begin就满足要求了，大于呆查找的的元素下标--begin\*\*(1)

class Solution {
    public:
        int searchInsert(int A[], int n, int target) {
            int begin = 0, end = n-1;
            int mid = 0;
            while(begin <= end){    // 二分查找+判断边界
                mid = (begin+end)/2;
                if(A[mid] == target) return mid;
                else if(A[mid] < target) begin = mid+1;
                else end = mid-1;
            }
            return begin;
            
        }
    };

**二： leetcode(34)——[Search for a Range][]**

题目：

Given a sorted array of integers, 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]`.

For example,  
Given `[5, 7, 7, 8, 8, 10]` and target value 8,  
return `[3, 4]`.

链接：https://leetcode.com/problems/search-for-a-range/

分析：当通过二分查找找到该元素时，我们并没有直接返回，而是通过判断begin和end处是否等于target，如果不等则通过begin++ 与end--逐渐逼近\*\*\*\*(2)

class Solution {
    public:
        vector<int> searchRange(int A[], int n, int target) {
            int begin = 0, end = n-1;
            vector<int> result(2, -1);
            while(begin <= end){
                int mid = (begin+end)>>1;
                if( A[mid]== target){
                    if(A[begin] == target && A[end] == target){  // 当中间值相等时直到左右区间都等于target才终止
                        result[0]= begin;    
                        result[1] = end;
                        break;
                    } 
                    if(A[begin] != target) begin++;        // 否则begin++ end--逐渐逼近
                    if(A[end] != target) end--;
                    
                }else if(A[mid] < target) begin = mid+1;
                else end = mid-1;
            }
            return result;
        }
    };

**三：leetcode(74)——[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.

For example,

Consider the following matrix:

[
      [1,   3,  5,  7],
      [10, 11, 16, 20],
      [23, 30, 34, 50]
    ]

Given target = `3`, return `true`.

链接：https://leetcode.com/problems/search-a-2d-matrix/

分析：此题通过两次二分查找，先确定元素所在的行，然后在行中进行二分查找即可。

class Solution {
    public:
        bool searchMatrix(vector<vector<int> > &matrix, int target) {
            int m = matrix.size();
            if(m == 0) return false;
            int n = matrix[0].size();
            int begin = 0, end = m-1;
            int mid = 0;
            while(begin <= end){                // 先对第一列进行二分查找找到元素所在行
                mid = (begin+end)/2;
                if(matrix[mid][0] == target) return true;
                else if(matrix[mid][0] < target) begin = mid+1;
                else end = mid-1;
            }
            
            int currentRow = 0;
            if(matrix[mid][0] > target) currentRow = mid -1;
            else currentRow = mid;
            if(currentRow < 0) return false;         
            begin = 0, end = n-1; 
            while(begin <= end){           // 然后对找到的行进行二分查找
                mid = (begin + end)/2;
                if(matrix[currentRow][mid] == target) return true;
                else if(matrix[currentRow][mid] < target)begin = mid+1;
                else end = mid-1;
            }
            return false;
        }
    };

**四：leetcode(153) [Find Minimum in Rotated Sorted Array][]**

题目：

Suppose a sorted array 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.

链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/

分析：此题这里给出三种方法，第一种是常规的普通法，一次遍历即可(不管数组是否有序)，时间复杂度为O(N)。第二种方法也是一样，据数据的特征，只要找到比num\[0\]小的元素就可以了，时间复杂度也是O(N)。第三种方法是二分查找，时间复杂度为O(lgN).

class Solution {
    public:
        /*9ms 法一：普通方法*/
        /*int findMin1(vector<int> &num) {
            int n = num.size();
            if(n == 0) return -1;
            int minMum = num[0];
            for(int i = 1; i < n; i++)
                minMum = min(num[i], minMum);
            return minMum;
        }*/
        
        /*法二：16ms*/
         /*int findMin(vector<int> &num) {
            int n = num.size();
            if(n == 0) return -1;
            if(num[0] <= num[n-1]) return num[0];
            
            int minMum = num[0];
            for(int i = 1; i < n; i++)
                if(num[i] < minMum) {
                    minMum = num[i];
                    break;
                }
            return minMum;
        }*/
        /*  法三：6ms */
        int findMin(vector<int> &num) {
            int n = num.size();
            if(n == 0) return -1;
            if(num[0] <= num[n-1]) return num[0];
            int begin = 0, end = n-1;
            while(begin < end){
                int mid = (begin+end)/2;   // 二分查找 判断在那一边即可
                if(num[mid] < num[begin]){
                    if(mid > 0 && num[mid] < num[mid-1])
                        return num[mid];
                    end = mid-1;
                }else{
                    if(mid < end && num[mid] > num[mid+1])
                        return num[mid+1];
                    begin = mid+1;
                }
            }
        }
        
        
    };

**因为内部有边界判断，故而用while(start < end-1)这样就能确保解方案内至少有3个元素在比较（\*\*\*\*\*（3）），所以代码可以变为： （通过mid与第一个元素s来判断在那边，然后进行后续操作）**

int findMin(vector<int> &num){
    	int n = num.size();
    	if(n == 0) return -1;
    	int s = 0, e = n-1;
    	if(num[0] < num[e]) return num[0];
    
    	while(s < e-1){     // 这样就确保了while循环内部至少有三个元素在比较
    		int mid = (s + e)>>1;
    		if(num[mid] < num[mid-1]) return num[mid];
    		if(num[mid] >= num[s]) s = mid+1;
    		else e = mid-1;
    	}
    	return num[e];
    }

**五：leetcode(154)**———[Find Minimum in Rotated Sorted Array II][]

题目：

> Follow up for "Find Minimum in Rotated Sorted Array":  
> What if duplicates are allowed?
> 
> Would this affect the run-time complexity? How and why?

Suppose a sorted array 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.

The array may contain duplicates.

链接：https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/

分析：这道题是第四题的变形，意在元素可以重复，这样的话，上述算法需要该进，只需要处理一种特殊情况，即当第一个元素和最后一个元素相同时，判断就无法知道最小值在哪，如212222222和2222222212，解决的方法是我们从找到第一个与最后一个元素不一样的值开始（\*\*\*（4））。

class Solution {
    public:
        int findMin(vector<int> &num) {
            int n = num.size();
            if(n == 0) return -1;
            
            int i = 0;
            if(num[0] == num[n-1]){    //  重复的话 就是 22222212 或者 212222222 当num[mid]== num[begin]时无法迭代
                for(i = 1; i < n; i++)    // 可以将当num[0] == num[n-1]时，找到第一个不等于num[0]的进行迭代 
                    if(num[i] != num[0])break;
            }
            if(i == n) return num[0];    // 全部是一样的元素
            if(num[i] < num[n-1]) return num[i];   // 判断是否本身有序了
            
            int begin = i, end = n-1;
            while(begin < end){
                int mid = (begin+end)/2;   // 二分查找 判断在那一边即可
                if(num[mid] < num[begin]){
                    if(mid > 0 && num[mid] < num[mid-1])
                        return num[mid];
                    end = mid-1;
                }else{
                    if(mid < end && num[mid] > num[mid+1])
                        return num[mid+1];
                    begin = mid+1;
                }
            }
        }
    };

这里提供discuss中的一种解法，只需要4ms

int findMin(int num[], int n) {
    
    int mid,begin,end;
    begin = 0;
    end = n - 1;
    while(begin <= end){
        mid = (begin + end) / 2;
        if(mid -1 >= 0 && num[mid] < num[mid - 1])
            return num[mid];
        else if(num[mid] > num[end])
            begin = mid + 1;
        else if(num[mid] < num[end])
            end = mid - 1;
        else
            end--;
    }
    
    return num[0];
    }

**六：leetcode(33)——[Search in Rotated Sorted Array][]**

题目：

Suppose a sorted array 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`).

You are given a target value to search. If found in the array return its index, otherwise return -1.

You may assume no duplicate exists in the array.

链接：https://leetcode.com/problems/search-in-rotated-sorted-array/

分析：这里提供两种方法：法医只要我们找到最小值O(N)时间，然后通过最后一个元素确定二分查找的区间就可以了，时间复杂度为O(N)。。法二为直接二分查找，不过判断要麻烦点，易出错，时间复杂度为O(lgN).

法一：

class Solution {
    public:
        int search(int A[], int n, int target) {
            if(n == 0) return -1;
            int minNum = A[0];
            int index = 0;
            for(int i = 1; i < n; i++){  // 找到最小元素
                if(A[i] < minNum){
                    minNum = A[i];
                    index = i;
                }
            }
            int begin = 0, end = n-1;      // 看在哪个区间 
            if(A[n-1] >= target)         // 注意这里是大于等于
                begin = index;
            else
                end = index-1;
                
            while(begin <= end){
                int mid = (begin+end)/2;
                if(A[mid] == target) return mid;
                else if(A[mid] < target) begin = mid+1;
                else end = mid-1;
            }
            return -1;
            
        }
    };

法二：

class Solution {
    public:   
        int search(int A[], int n, int target) {
            if(n == 0) return -1;
            int begin = 0, end = n-1;
            while(begin <= end){
                int mid = (begin + end) >> 1;
                if(A[mid] == target) return mid;
                if(A[mid] < A[begin]){     // 表示在后半部分
                    if(A[mid] > target || target >= A[begin]) end = mid-1;  
                    else begin = mid+1;
                }else{
                    if(A[mid] < target || target < A[begin]) begin = mid+1;
                    else end = mid-1;
                }
                
            }
            return -1;
        }
    };

注意这里后半部分判断是按照A\[mid\]与A\[begin\]来比较大小的比较清楚，如果按照A\[mid\]与target方法来判断也是可以的，就是麻烦一点。其实是相反的，上下都一样，判断一边就可以了。。。

int rotationArray(int *arr, int n, int target){
    	int s = 0, e = n-1;
    	while(s <= e){
    		int mid = (s+e) >> 1;
    		if(arr[mid] == target) return mid;
    		else if(target > arr[mid]){
    			if(arr[mid] >= arr[s] || target < arr[s]) s= mid+1;
    			else e = mid -1;
    		}
    		else{
    			if(arr[mid] < arr[s] ||  target >= arr[s]) e= mid-1;
    			else s = mid+1;
    		
    		}
    	
    	}
    	return -1;
    }

**七：leetcode(81)——** [Search in Rotated Sorted Array II][]

题目：

Follow up for "Search in Rotated Sorted Array":  
What if duplicates are allowed?

Would this affect the run-time complexity? How and why?

Write a function to determine if a given target is in the array.

链接：https://leetcode.com/problems/search-in-rotated-sorted-array-ii/

分析：法一：这里要求元素可以重复，因此我们需要找到紧靠最大值的最小即可，其它思路和上题一模一样。。法二也是二分查找，但是和第五题思路一样，需要对上一题进行改进，去除前面和尾部相同的元素。

法一：

class Solution {
    public:
        bool search(int A[], int n, int target) {
            if(n == 0) return false;
            int minNum = A[0];
            int index = 0;
            for(int i = 1; i < n; i++){  // 找到最小元素
                if(A[i] <= minNum && A[i-1] > A[i]){         // 只改变了一点 确保最大值最小值相邻
                    minNum = A[i];
                    index = i;
                }
            }
            int begin = 0, end = n-1;      // 通过A[n-1]看在哪个区间 
            if(A[n-1] >= target)         // 注意这里是大于等于
                begin = index;
            else
                end = index-1;
                
            while(begin <= end){
                int mid = (begin+end)/2;
                if(A[mid] == target) return true;
                else if(A[mid] < target) begin = mid+1;
                else end = mid-1;
            }
            return false;
        }
    };

法二：

class Solution {
    public:    
         bool search(int A[], int n, int target) {
            if(n == 0) return false;
            int i = 0;
            if(A[0] == target) return true;
             if(A[0] == A[n-1]){    //  与没有重复元素的差别就在于前后元素是否一样，一样就无法比较
                for(i = 1; i < n; i++)    
                    if(A[i] != A[0])break;
            }
            int begin = i, end = n-1;
            while(begin <= end){
                int mid = (begin + end) >> 1;
                if(A[mid] == target) return true;
                if(A[mid] < A[begin]){
                    if(A[mid] > target || target >= A[begin]) end = mid-1;    // 判别条件
                    else begin = mid+1;
                }else{
                    if(A[mid] < target || target < A[begin]) begin = mid+1;
                    else end = mid-1;
                }
                
            }
            return false;
            
        }
    };

八：leetcode(162) [Find Peak Element][]

题目：

A peak element is an element that is greater than its neighbors.

Given an input array where `num[i] ≠ num[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 `num[-1] = num[n] = -∞`.

For example, in array `[1, 2, 3, 1]`, 3 is a peak element and your function should return the index number 2.

链接：https://leetcode.com/problems/find-peak-element/

分析：此题关键在于元素的分布情况，理解了分布情况就知道怎么用二分查找了。因为`num[-1] = num[n] = -∞`.因此当num\[mid\]的一边num\[mid-1\]或者num\[mid+1\]有一个大于num\[mid\]时，大于的那一边一定存在peak element，因此可以在logN时间内完成

class Solution {
    public:
        /*int findPeakElement(const vector<int> &num) {
            int n = num.size();
            if(n <= 1) return 0;
            
            for(int i = 1; i < n-1; i++){
                if(num[i]> num[i-1] && num[i] > num[i+1])return i;
            }
            if(num[n-1] > num[n-2]) return n-1;
            return 0;
            
        }*/
        int findPeakElement(const vector<int> &num) {
            int start = 0, end = num.size()-1;
            while(start < end-1){
                int mid = (start+end) >> 1;
                if(num[mid] > num[mid+1] && num[mid] > num[mid-1]) return mid;
                else if(num[mid] > num[mid+1]) end = mid-1;
                else start = mid+1;
            }
            return num[start] < num[end]? end:start;
        }
    };

注意while(start < end-1)这种边界判断就能保证始终有大于等于3个元素在内部比较，就可以有mid-1和mid+1不需要判断越界问题了。。

[Search Insert Position]: https://leetcode.com/problems/search-insert-position/
[Search for a Range]: https://leetcode.com/problems/search-for-a-range/
[Search a 2D Matrix]: https://leetcode.com/problems/search-a-2d-matrix/
[Find Minimum in Rotated Sorted Array]: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/
[Find Minimum in Rotated Sorted Array II]: https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/
[Search in Rotated Sorted Array]: https://leetcode.com/problems/search-in-rotated-sorted-array/
[Search in Rotated Sorted Array II]: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/
[Find Peak Element]: https://leetcode.com/problems/find-peak-element/