Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

1. Title Description

Source: LeetCode

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: 4Copy the code

Example 2:

Input: nums = [4,5,6,7,0,1,2], target = 3 output: -1Copy the code

Example 3:

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

Tip:

  • 1 <= nums.length <= 5000
  • -10^4 <= nums[i] <= 10^4
  • Each value in NUMS is unique
  • The problem data guarantees that NUMS is rotated at some previously unknown subscript
  • -10^4 <= target <= 10^4

Two, train of thought analysis

dichotomy

Because the array is sorted in ascending order, and when the array is rotated at k, the rotated array satisfies

  • The first half >num[0]
  • The second half of the <num[0]

We can use this condition to find the point of rotation, k, and then

  • judgetarget 和 Pivot pointValue of, judgetargetIs it in the first half or the second half
  • And then in the half section of the falling point again binary search targettarget

Three, code implementation

class Solution { public int search(int[] nums, int target) { int length = nums.length; if (length == 0) return -1; if (length == 1) return nums[0] == target ? 0:1; Int l = 0, r = length-1; while (l < r) { int mid = l + r + 1 >> 1; if (nums[mid] >= nums[0]) { l = mid; } else { r = mid - 1; If (target >= nums[0]) {l = 0; if (target >= nums[0]) {l = 0; } else { l = l + 1; r = length - 1; } // select target while (l < r) {int mid = l + r + 1 >> 1; if (nums[mid] <= target) { l = mid; } else { r = mid - 1; } } return nums[r] == target ? r : -1; }}Copy the code

Complexity analysis

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

The results

conclusion

This problem also allows binary search, but it takes two times, the first time to find the rotation point and the second time to find the target.

Finding the subscript of a certain number in an ordered sequence by dichotomy is just an application of dichotomy. The essence of dichotomy is to find the boundary of properties.

So it can be used for more than just finding a number in an ordered sequence

Keep it up