Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

33. Search a rotated sort array

Find the index of the target element in a rotated array with no duplicate elements in ascending order. The rotation is to rotate a [0,1,2,4,5,6,7,0,1,2] array to [4,5,6,7,0,1,2].

Answer:

If the array has not been rotated by the topic, it is easy to find the subscript of the target element using binary lookup. And we can analyze the way to solve the problem based on that. After “rotate”, while the new array is no longer a full array of ascending, but it still can be sequenced in a sense, it consists of two ascending array, and the right part of the largest element of an array of ascending to less than the minimum elements of the left raw ordinal group, is the first element of the array is greater than the last element.

Based on this, this problem can still use the binary search method to find the subscript of the target element, but the condition judgment is more complicated.

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                // The middle pointer falls on the left part of the ascending sequence
            } else {
                // The middle pointer falls on the right part of the ascending sequence}}return -1; }}Copy the code

In both cases, you need to make a judgment:

  • When meetnums[0] <= nums[mid], that is, the middle pointer falls on the left half of the ascending sequence, then, if the size of the target value is innums[l] 和 nums[mid], then the subscript of the target value (if any) is to the left of mid, and the r pointer is moved tomid - 1The location of the. Otherwise, move the L pointer tomid + 1The location of the.
  • If the above conditions are not met, it represents the rising narrative crack with the middle falling on the right half. At this time, it needs to judge if the size of the target value is innums[mid] 和 nums[r], then the subscript of the target value (if any) is to the right of mid, move the L pointer tomid + 1The location of the. Otherwise, move the r pointer tomid - 1The location of the.

Final code:

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int l = 0, r = n - 1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if (target == nums[mid]) {
                return mid;
            }
            if (nums[0] <= nums[mid]) {
                if (nums[l] <= target && target < nums[mid]) {
                    r = mid - 1;
                } else {
                    l = mid + 1; }}else {
                if (nums[mid] < target && target <= nums[r]) {
                    l = mid + 1;
                } else {
                    r = mid - 1; }}}return -1; }}Copy the code