preface

A rotated sorted array is an array that has been rotated in ascending order at some previously unknown point (for example, the array [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2]). There are three questions related to this in LeetCode, and the following are specific analysis of these three questions.

Search rotated sorted arrays (LeetCode 33 problem)

Searches for a given target value, returning its index if it exists in the array, or -1 otherwise. You can assume that there are no duplicate elements in the array. Your algorithm must be order log n in time.

Example 1:

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

Example 2:

  • Input: nums = [4,5,6,7,0,1,2], target = 3
  • Output: 1

Source: LeetCode link: leetcode-cn.com/problems/se… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Analysis of the

  • If the time complexity is O(logn), we must use dichotomy. The sequence after rotation is I ~ N-1, 0 ~ I-1. Because the array itself is arranged in ascending order, the position of the middle node of mid can be carefully analyzed to find the breakthrough of this problem. Assuming that mid is in the range of I ~ N-1, So the segment I ~ mid is ordered, whereas mid ~ I -1 is disordered. When mid node is in the range of 0 ~ I -1, it is easy to know that mid ~ I -1 is orderly, and I ~ mid is disordered. As you can see, no matter where mid is, there’s always an ordered segment, and ultimately we’re using the ordered segment to exclude half of the data at a time.

  • To analyze the ordered segment, look at the problem again, because the array is in ascending order, we only need to compare each time to the node on the right. If nums[mid] < nums[right], mid to right is ordered. If nums[mid] > nums[right], mid to right is ordered. If nums[mid] > nums[right], mid to right is ordered. That is, the segment is disordered. According to the above analysis, no matter which segment mid is in, there is always an ordered interval. Therefore, the i-mid segment is ordered at this time.

  • Once we have the ordered segment, we can select half of the data based on whether target exists in the ordered segment or not. The final code is as follows:

    public int search(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] == target) {
                return mid;
            }
            if (nums[mid] > nums[right]) {
                // Whether target exists in the left ~ mid ordered segment
                if (nums[left] <= target && nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1; }}else {
                // Whether target exists in the ordered segment mid ~ right
                if (nums[right] >= target && nums[mid] < target) {
                    left = mid + 1;
                } else {
                    right = mid - 1; }}}return -1;
    }
Copy the code

Complexity analysis

  • Time complexity: the binary search is O(logn) because half of the data is rejected each time.
  • Space complexity: No extra space used, O(1).

Finding the minimum value in a rotated sorted array (LeetCode153)

Analysis of the

  • The minimum value is the same as the minimum value. Recall the previous analysis again. Assuming that the rotation is performed at the subscript I, the sequence after rotation is I ~ n-1 and 0 ~ i-1. For mid node, it can be known from the previous analysis that whether the ordered interval is before or after mid can be determined by the relationship between the value of mid node and the rightmost node. The ordered interval is analyzed again. Assuming that the segment I ~ mid is ordered, the array must be rotated at a certain position in the segment mid ~ I -1. Accordingly, the minimum value also exists in this interval, that is, in the disordered segment. When mid ~ i-1 is ordered, according to the above analysis, the minimum value must also exist in the interval with rotating nodes, namely the disordered segment.

  • After the above analysis, it can be seen that the minimum value (i.e., the rotation node) must exist in the unordered segment, so the code can be easily obtained as follows:

    public int findMin(int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right) {
            int mid = (left + right) >>> 1;
            // mid > right;
            // Left ~ mid is an ordered segment
            if (nums[mid] > nums[right]) {
                left = mid + 1;
            } else {
                // mid < right, mid may be the smallest,
                // For the ordered segment mid ~ right, we can only discard mid+1 ~ rightright = mid; }}return nums[left];
    }
Copy the code

Complexity analysis

  • Time complexity: O(logn);
  • Space complexity: O(1).

An array with duplicate values

The above two questions do not consider the duplicate elements in the array, while questions 81 and 154 of Leetcode have the changes of duplicate elements in the above two questions. When there are repeated elements, there will be one more possible equal case when judging the size of mid and right node, so how to consider equality? In fact, we only need to use right– every time when judging the equality case, because whether we are looking for the target value or the minimum value of the array, since mid is equal to right, we can get the final result by removing the right-most node every time and then judging the remaining part. However, in the case of duplicate values, the time complexity of the algorithm also changes, and in the best case (there are no duplicate elements in the array), there is still no O(logn). But in the worst case (the array elements are all equal), since you can only shrink the array by one at a time, it will degenerate to O(n).