This is the sixth day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

Search rotation sort array

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:
Enter: nums = [4.5.6.7.0.1.2], target = 0Output:4
Copy the code
Example 2:
Enter: nums = [4.5.6.7.0.1.2], target = 3Output: -1
Copy the code
Example 3:
Enter: nums = [1], target = 0Output: -1
Copy 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
Advanced:

Can you design a solution in order log n time?

The problem solving

Their thinking

A simple dichotomy is to set a left and right pointer, and determine the relationship between mid and target value.

In this case, only part of the array is ordered due to rotation, so we need to add a judgment condition in advance, and compare the value of mid with the value of right each time.

Binary search. But when you rotate it, you have two ordered segments. And the dichotomy is essentially the test for A or B, or 0/1. Thus narrowing the search space. As long as the essence of “dichotomy” can be satisfied, we can try to solve the problem by dichotomy.

This is not a monotone ordered array. But it satisfies the dichotomous nature. You can divide the search space into two halves (the first half or the second half) by some criteria.

The problem solving process

Firstly, through the element of mid position and the first element of array (or the last element can be selected), the position of inflection point is identified before or after mid, so that it can be known that [left,mid] or [mid,right] is monotonic. In this case, the first element of the array is used to help identify.

Details are as follows:

Nums (mid) > nums(left); nums(left,mid) > nums(left,right); Mid (mid) < nums(left,right); mid (left,right) < nums(left,right); After the monotonicity of before [left,mid] or after [mid,right] is known from <1>, the boundary values of target and monotone interval are introduced for comparison. <2-1> Target == nums(mid); If (nums(left) <= target (mid), right = mid; if (mid) <= target (left), right = mid; If (mid,right) left = mid+1; If (mid (mid) < target <= nums(right), left = mid (mid) + 1; Otherwise, right = mid (left,mid), right = mid (right,mid);

【 note 】 discriminant conditions in detail is exactly is “> =”, or “>” (or “< =” or “<“), with or without “=”, need to pay attention to. It’s best to take a few examples and run through them.

Code implementation

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        int res = -1;
        int left = 0, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            / / find
            if (nums[mid] == target) {
                res = mid;
                break;
            }
            // There is rotation in the left half and order in the right half
            if (nums[mid] < nums[left]) {
                / / on the right
                if (nums[mid] < target && target <= nums[right-1]) {
                    left = mid + 1;
                } else { / / on the left sideright = mid; }}else { // The left half has no rotating part, and the left half is orderly
                / / on the left side
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid;
                } else { / / on the right
                    left = mid + 1; }}}returnres; }}Copy the code

If nums[mid] == nums[left], select * from left where nums[mid] == nums[left], select * from left where nums[mid] == nums[left]

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n;
        while (left < right) {
            int mid = left + (right - left) / 2;
            / / find
            if (nums[mid] == target) {
                return true;
            }
            // There is no rotation in the left half
            if (nums[mid] == nums[left]) {
                left++;
                continue;
            }
            // There is rotation in the left half and order in the right half
            if (nums[mid] < nums[left]) {
                / / on the right
                if (nums[mid] < target && target <= nums[right-1]) {
                    left = mid + 1;
                } else { / / on the left sideright = mid; }}else { // The left half has no rotating part, and the left half is orderly
                / / on the left side
                if (nums[left] <= target && target < nums[mid]) {
                    right = mid;
                } else { / / on the right
                    left = mid + 1; }}}return false; }}Copy the code

My thoughts and methods about searching rotated sorted array are shared here today. If you want to see what problems are solved in the algorithm interview, you can leave a message to me and we will discuss it together. See you in the next article.