LeetCode - Search in Rotated Sorted Array II
Problem description
Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,0,1,2,2,5,6] might become [2,5,6,0,0,1,2]).
You are given a target value to search. If found in the array return true, otherwise return false.
Example 1:
1
2
Input: nums = [2,5,6,0,0,1,2], target = 0
Output: true
Example 2:
1
2
Input: nums = [2,5,6,0,0,1,2], target = 3
Output: false
Follow up:
- This is a follow up problem to Search in Rotated Sorted Array, where nums may contain duplicates.
- Would this affect the run-time complexity? How and why?
Analysis
The general idea is to use binary search.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public boolean search(int[] nums, int target) {
int low = 0;
int high = nums.length - 1;
while (low <= high){
int mid = low + (high - low) / 2;
int m = nums[mid];
if (m == target){
return true;
}
int l = nums[low];
int h = nums[high];
if (l < m){
if (target < m && target >= l){
high = mid - 1;
}
else {
low = mid + 1;
}
}
else if (l > m){
if (target > m && target <= h){
low = mid + 1;
}
else{
high = mid - 1;
}
}
else{
low++;
}
}
return false;
}
}
What to improve
- need summarize for binary search.