Question
Formatted question description: https://leetcode.ca/all/81.html
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up for "Search in Rotated Sorted Array":
What if duplicates are allowed?
Would this affect the run-time complexity? How and why?
Write a function to determine if a given target is in the array.
@tag-array
Algorithm
Since the previous question Search in Rotated Sorted Array does not have the same value, when we compare the middle value and the rightmost value, we are in full compliance with the previous rule:
- if the number in the middle is less than the rightmost number, the right half is in order.
- If the number is greater than the rightmost number, the left half is ordered.
And if there can be repeated values, there will be two situations, [3 1 1] and [1 1 3 1]. For these two situations, when the intermediate value is equal to the rightmost value, the target value 3 can be either on the left or on the right.
It can be on the right, then what should we do? In this case, it is actually very simple. Just move the rightmost value to the left to continue the loop. If it is still the same, continue to move until it reaches a different value, and then the other parts are still Use the method in Search in Rotated Sorted Array
Code
Java
public class Search_in_Rotated_Sorted_Array_II {
// time: O(1)
// space: O(N)
public class Solution {
public boolean search(int[] nums, int target) {
if (nums == null || nums.length == 0) {
return false;
}
int i = 0; // left pointer
int j = nums.length - 1; // right pointer
while(i <= j) {
int mid = (i + j) / 2;
if (nums[mid] == target) {
return true;
}
// @note: if (nums[0] <= nums[mid]) {
if (nums[i] <= nums[mid]) { // left half ordered, right half not ordered
// if (target <= nums[mid]) {
if (nums[i] <= target && target <= nums[mid]) {
j = mid;
} else {
i++;
}
} else { // right half ordered, left half not ordered
// if (target <= nums[mid]) {
if (nums[mid] <= target && target <= nums[j]) {
i = mid;
} else {
j--;
}
}
}
return false;
}
}
}