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; } } }
-
// OJ: https://leetcode.com/problems/search-in-rotated-sorted-array-ii/ // Time: average O(logN), worst O(N) // Space: O(1) class Solution { int findStart(vector<int> &A) { int L = 0, R = A.size() - 1; while (L + 1 < R) { if (A[L] < A[R]) return L; int M = (L + R) / 2; if (A[M] > A[R]) L = M + 1; else if (A[M] < A[R] || (A[M] == A[R] && A[L] > A[R])) R = M; else { int k = L; while (k < R && A[L] == A[k]) ++k; if (k == R) return L; if (A[k] < A[L]) return k; L = k + 1; } } return A[L] < A[R] ? L : R; } public: bool search(vector<int>& A, int T) { if (A.empty()) return false; int start = findStart(A), N = A.size(), L = 0, R = N - 1; while (L <= R) { int M = (L + R) / 2, mid = (start + M) % N; if (A[mid] == T) return true; if (A[mid] < T) L = M + 1; else R = M - 1; } return false; } };
-
class Solution(object): def search(self, nums, target): """ :type nums: List[int] :type target: int :rtype: bool """ start, end = 0, len(nums) - 1 while start + 1 < end: mid = start + (end - start) / 2 if nums[mid] == target: return True if nums[start] < nums[mid]: if nums[start] <= target <= nums[mid]: end = mid else: start = mid elif nums[start] > nums[mid]: if nums[mid] <= target <= nums[end]: start = mid else: end = mid else: start += 1 if nums[start] == target: return True if nums[end] == target: return True return False