Local ordering of binary search

We already know that binary search is a search algorithm for finding a specific element in an ordered array.

What if an array is not globally ordered, but locally ordered? At this time, we can use the divide and conquer strategy. We can perform binary search in the locally ordered interval, and then combine each local result to form the overall result.

153 find the smallest value in the rotation sort array

An array of length n is known, which is arranged in ascending order in advance. After 1 to n rotations, the input array is obtained. Array [a [0], a [1], a [2], The result of a [n-1]] rotation is array [a [n-1], a [0], a [1], a [2], a[n-2]].

Input an array with different elements, and output an integer value to represent the minimum value of the array.

Input: num = [4,5,6,7,0,1,2]
Output: 0
Explanation: the original array is [0,1,2,4,5,6,7]. Rotate it for 4 times to get the input array.

Resolution:

An ascending array without duplicate elements can be directly divided into two parts after rotation. For example, the array [4,5,6,7,0,1,2] can be divided into two parts [4,5,6,7] and [0,1,2]. It can be seen that the minimum value of the array is the dividing point of the two locally ordered intervals of the rotating array.

How do we find this dividing point? Because the array is globally ordered before rotation, Num [0] is the center of rotation after rotation. After rotation, the elements in one part of the array are greater than or equal to num [0], and the elements in the other part are less than num [0].

Using this feature, we use the binary search method to find the dividing point between the two parts of the rotating array:

• Start from the middle. If the value of the current search is greater than or equal to num [0], the dividing point is left = mid+1 on the right side of mid
• If the value of the current search is less than num [0], the dividing point is on the left side of mid, right = mid
• Cycle the above steps and finally find the dividing point left == right

Of course, we should consider a special case: the array with length n rotates N and returns to its original state. In this case, we can't find the minimum value by finding the dividing point above, because in this case, the rotation array can't be divided into two parts: the locally ordered interval greater than or equal to num [0] and the locally ordered interval all less than num [0]. However, it is easy to find the minimum value in this case, which is num [0], and it is easy to judge that the first element of the array is smaller than the tail element, indicating that the array is orderly as a whole.

class Solution {
public:
    int findMin(vector<int>& nums) {
        int left = 0, right = nums.size();
        // Num [left] < num [Right-1] judge whether the array is ordered as a whole
        // Num [left] = = num [Right-1] judge whether the array has only one element
        if(nums[left]<=nums[right-1]){
            return nums[left];
        }
        // Binary search finds the boundary, that is, the minimum value
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] < nums[0]){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return nums[left];
    }
};

154 find the minimum value II in the rotation sort array

An array of length n is known, which is arranged in ascending order in advance. After 1 to n rotations, the input array is obtained. Array [a [0], a [1], a [2], The result of a [n-1]] rotation is array [a [n-1], a [0], a [1], a [2], a[n-2]].

Enter an array with possible duplicate elements and output an integer value to represent the minimum value of the array.

Input: num = [2,2,2,0,1,2]
Output: 0

Resolution:

This topic and 153 find the smallest value in the rotation sort array The solution is the same. The only difference is that we need to consider the repetition of elements.

In the case of rotation, we still find the minimum value in the array by looking for the dividing point, or divide the array into two parts greater than or equal to num [0] and less than num [0] according to the characteristics of the rotating array with num [0] as the reference value.

However, if there are duplicate elements, the division of this two classification will not be realized. For example [2,3,0,1,2,2,2,2], we divide it into [2,3] and [0,1,2,2,2,2,2], obviously [0,1,2,2,2,2] does not satisfy the condition that all are less than num [0] = = 2. In this case, we cannot correctly use binary search to find the dividing point. For example, in the first cycle in the above example, Num [mid] = = num [4] = = 2, which will lead to finding the dividing point to the right. Obviously, it cannot be found.

So how can we restore the dichotomous property of a rotating array with duplicate elements?

It can be observed that the dichotomous property of the rotating array is destroyed only when the repeating element is used as the rotation center. The recovery method is also very simple. You only need to delete the elements equal to num [0] in the local interval less than num [0], that is, delete the elements equal to num [0] at the end of the rotating array. This operation does not affect the judgment of the overall minimum value of the array, and also restores the dichotomous property of the rotating array.

class Solution {
public:
    int findMin(vector<int>& nums) {
        // Delete the elements at the end of the rotation array equal to num [0]. Tail > 0. If the array elements are all the same, keep num [0]
        int tail = nums.size()-1;
        while(tail>0){
            if(nums[tail]==nums[0]){
                --tail;
            }else{
                break;
            }
        }
		
        // Num [left] < num [Right-1] judge whether the array is ordered as a whole
        // Num [left] = = num [Right-1] judge whether the array has only one element	
        int left = 0, right = tail+1;
        if(nums[left]<=nums[right-1]){
            return nums[left];
        }
        // Binary search finds the boundary, that is, the minimum value
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] < nums[0]){
                right = mid;
            }else{
                left = mid+1;
            }
        }
        return nums[left];
    }
};

33 search rotation sort array

An array that was originally ordered incrementally is disconnected at a certain position after being connected end to end (e.g. [0,1,2,4,5,6,7] → [4,5,6,7,0,1,2], disconnected at bit 4). We call it a rotating array. Given a value, judge whether the value exists in the rotating array.

The input is an array and a value, and the output is an integer value indicating the position of the target value in the rotation array. If it does not exist, it returns - 1.

Input: num = [4,5,6,7,0,1,2], target = 0
Output: 4

Resolution:

When we observe this so-called rotation array, we can see that the array [4,5,6,7,0,1,2] can be divided into two ordered parts, namely [4,5,6,7] and [0,1,2]. Therefore, we can use binary search to search the target value in these two locally ordered parts.

Based on the above ideas, we need to complete two tasks:

• Find the dividing point to divide the local order
• Use binary lookup to search for the target value in a locally ordered array

In the first task, we can quickly find the dividing point by using the property of rotating array. The two locally ordered parts of the rotated array can be divided by a simple property: because the array is globally ordered before rotation, Num [0] is the center of rotation after rotation. Then, in the two locally ordered parts of the rotated array, the elements in one part are greater than or equal to num [0], and the elements in the other part are less than num [0].

Using this feature, we use the binary search method to find the dividing point between the two parts of the rotating array:

• Start from the middle. If the value of the current search is greater than or equal to num [0], the dividing point is left = mid+1 on the right side of mid
• If the value of the current search is less than num [0], the dividing point is on the left side of mid, right = mid
• Cycle the above steps and finally find the dividing point left == right

In the second task, we can still directly compare the target value target with num [0] Based on the characteristics of the rotation array, and select the corresponding local ordered interval for binary search.

Of course, you can also use the divide and conquer strategy. Instead of comparison, you can directly divide the two intervals according to the dividing point. At the same time, you can use the binary search to search the target value target in the two intervals to return the final result composed of multiple local results.

class Solution {
public:
    int binarySerach(vector<int> nums, int target, int leftBound, int rightBound){
        int left = leftBound, right = rightBound;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                return mid;
            }else if(nums[mid] > target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return -1;
    }

    int search(vector<int>& nums, int target) {
        // Use binary search to find the dividing point and divide the array into two parts greater than or equal to num [0] and less than num [0]
        int left = 0, right = nums.size();
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] < nums[0]){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
		// If the target value is less than nums[0], search the target value with binary search in the local ordered interval on the right side of the dividing point
        if(nums[0] > target){
            return binarySerach(nums,target,left,nums.size());
        }else{
            // If the target value is greater than or equal to nums[0], search the target value with binary search in the local ordered interval on the left of the dividing point
            return binarySerach(nums,target,0,left);
        }
    }
};

81 search rotation sort array II

An array with duplicate elements and originally increased order is disconnected according to a certain position after being connected end to end (e.g. [0,0,1,2,2,5,6] → [2,5,6,0,0,1,2], disconnected in bit 4). We call it a rotating array. Given a value, judge whether this value exists in the rotating array.

The input is an array and a value, and the output is a Boolean value indicating whether the value exists in the array.

Input: num = [2,5,6,0,0,1,2], target = 0
Output: true

Resolution:

This topic and 33 search rotation sort array The solution is the same. The only difference is that we need to consider the repetition of elements.

Similarly, we can divide the rotation array into two locally ordered parts by finding the dividing point, and use binary search to search the target value in the locally ordered interval. We still need to accomplish two tasks:

• Find the dividing point to divide the local order
• Use binary lookup to search for the target value in a locally ordered array

To find the dividing point, we still divide the array into two parts greater than or equal to num [0] and less than num [0] according to the characteristics of the rotating array and taking num [0] as the reference value.

However, if there are duplicate elements, the division of this two classification will not be realized. For example [2,5,6,0,0,1,2], we divide them into [2,5,6] and [0,0,1,2]. Obviously [0,0,1,2] does not satisfy the condition that they are all less than nums[0]==2.

So how can we restore the dichotomous property of a rotating array with duplicate elements?

It can be observed that the dichotomous property of the rotating array is destroyed only when the repeating element is used as the rotation center. The recovery method is also very simple. You only need to delete the elements equal to num [0] in the local interval less than num [0], that is, delete the elements equal to num [0] at the end of the rotating array. This operation does not affect the judgment of the existence of elements, and also restores the dichotomous property of rotating arrays.

The problem of repeating elements is solved, and the other steps are the same as 33 search rotation sort array The solution is consistent.

class Solution {
public:
    bool  binarySearch(vector<int> nums, int target, int leftBound, int rightBound){
        int left = leftBound, right = rightBound;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] == target){
                return true;
            }else if(nums[mid] > target){
                right = mid;
            }else{
                left = mid + 1;
            }
        }
        return false;
    }

    bool search(vector<int>& nums, int target) {
        // Delete the elements at the end of the rotation array equal to num [0]. Tail > 0. If the array elements are all the same, keep num [0]
        int tail = nums.size()-1;
        while(tail>0){
            if(nums[tail]==nums[0]){
                --tail;
            }else{
                break;
            }
        }
        
        // Use binary search to find the dividing point and divide the array into two parts greater than or equal to num [0] and less than num [0]
        int left = 0, right = tail+1;
        while(left<right){
            int mid = left + (right-left)/2;
            if(nums[mid] < nums[0]){
                right = mid;
            }else{
                left = mid+1;
            }
        }
		
        // If the target value is less than nums[0], search the target value with binary search in the local ordered interval on the right side of the dividing point
        if(nums[0] > target){
            return binarySearch(nums,target,left,nums.size());
        }else{
            // If the target value is greater than or equal to nums[0], search the target value with binary search in the local ordered interval on the left of the dividing point
            return binarySearch(nums,target,0,left);
        }
    }
};

4 find the median of two positively ordered arrays

Give two positively ordered (from small to large) arrays nums1 and nums2 of size m and n. find and return the median of these two positively ordered arrays.

Input two ordered arrays and output a floating-point value to represent the median of the two arrays. The time complexity of the algorithm should be O(log (m+n)).

Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merge array = [1,2,3], median 2

Resolution:

This question is not fully understood and needs to be updated

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        if (tot % 2 == 0) {
            int left = find(nums1, 0, nums2, 0, tot / 2);
            int right = find(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;
        } else {
            return find(nums1, 0, nums2, 0, tot / 2 + 1);
        }
    }

    int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k) {
        if (nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);
        if (k == 1) {
            if (nums1.size() == i) return nums2[j];
            else return min(nums1[i], nums2[j]);
        }
        if (nums1.size() == i) return nums2[j + k - 1];
        int si = min((int)nums1.size(), i + k / 2), sj = j + k - k / 2;
        if (nums1[si - 1] > nums2[sj - 1])
            return find(nums1, i, nums2, sj, k - (sj - j));
        else
            return find(nums1, si, nums2, j, k - (si - i));
    }
};

reference material

LeetCode 101: easily brush questions with you (C + +) Chapter 4 Juhe chop! Binary search

One article takes you to brush two points to find (Video + drawing)