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.