This is the 30th day of my participation in the Wenwen Challenge

preface

Search the rotation sort array as follows:

The integer array NUMs is sorted in ascending order, with different values in the array.

Before passing to the function, nums is rotated on some previously unknown subscript k (0 <= k < nums.length), Make the array [nums [k], nums [k + 1),…, nums] [n – 1, nums [0], nums [1],…, nums [k – 1]] (subscript starting from 0). ,1,2,4,5,6,7 [0], for example, in the subscript 3 after rotation may become,5,6,7,0,1,2 [4].

Give you the rotated array nums and an integer target, return its subscript if nums contains the target value, otherwise -1.

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

Example 3:

Input: nums = [1], target = 0 Output: -1

A, thinking

The questions are very long and can be confusing, so you need to read them several times to get the meaning.

There are two key messages in the title:

  • The original array nums is in ascending order and has different values
  • The actual input nums is rotated, which means that as long as the rotation point is not subscript 0, nums is an ascending and then descending permutation

Once you know the key information, you can use dichotomy to quickly locate the target. During iteration, there are several situations

  1. nums[mid] == target, directly return the subscript
  2. nums[mid] < nums[right]instructionsIt must be in ascending order from mid to the right(Since nums is rotated from a certain position, if the median value is less than the rightmost value, mid is either at or to the right of the rotation point.)
  3. nums[mid] > nums[right] It must be in ascending order from left to mid

For example

Here nums = [4,5,6,7,0,1,2] and target = 0 in example 1 are examples

The specific steps of dichotomy are as follows:

  1. The initialization valueleft = 0.right = 6
  2. The first stepmid = (left + right)/2 = 3At this time,nums[mid] > nums[right], 7 > 2That at this time0 ~ midIt’s in ascending order. And becausetarget < nums[mid], 0 < 7That means the value might be on the right-hand side, soleft = mid + 1 = 4
  3. The third stepmid = (left + right)/2 = 5At this time,nums[mid] < nums[right], 1 < 2So it must be in ascending order from the middle to the right. And becausetarget < nums[mid], 0 < 1That means it’s probably in the left half, soright = mid -1 = 4
  4. The fourth stepmid = (left + right)/2 = 4At the right timenums[4] == target, 4 == 4, returns the subscript4As a result

Second, the implementation

The implementation code

The implementation code is consistent with the idea, mainly is to know which side should be discarded to reduce the number of traversal, the time complexity of dichotomy is O(logN)

    /** * dichotomy */
    public int search(int[] nums, int target) {
        int len = nums.length;
        int left = 0;   / / the left border
        int right = len -1; / / right border
        while (left <= right) {
            int mid = (right + left) / 2;
            if (nums[mid] == target) {
                return mid;
            }
            // The right half is in ascending order
            else if (nums[mid] < nums[right]) {
                if (nums[mid] < target && target <= nums[right]) {
                    // If the value is in the right half, discard the left half
                    left = mid + 1;
                } else {
                    // Other circumstances
                    right = mid - 1; }}// Left half ascending
            else {
                if (nums[left] <= target && target < nums[mid]) {
                    // If the value is in the left half, discard the right half
                    right = mid - 1;
                } else {
                    left = mid + 1; }}}return -1;
    }
Copy the code

The test code

    public static void main(String[] args) {
        int[] nums = {4.5.6.7.0.1.2};
        int ret = new Number33().search(nums, 0);
        System.out.println(ret);
    }
Copy the code

The results of

Third, summary

Thank you to see the end, very honored to help you ~♥