Difficulty | Related Topics | Similar Questions | ||||||
---|---|---|---|---|---|---|---|---|
Medium |
|
|
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:
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:
- 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?
See 33. Search in Rotated Sorted Array. The code is basically the same. Except with duplicates we can not tell which way to jump when pivot == nums[e]
. The only thing we can do is to ditch nums[e]
. SO worst case O(*n*)
.
/**
* @param {number[]} nums
* @param {number} target
* @return {boolean}
*/
var search = function(nums, target) {
let s = 0
let e = nums.length - 1
while (s <= e) {
const p = (e + s) / 2 | 0
const pivot = nums[p]
if (target === pivot) {
return true
}
if (pivot < nums[e]) {
if (target > nums[p] && target <= nums[e]) {
s = p + 1
} else {
e = p - 1
}
} else if (pivot > nums[e]) {
if (target < nums[p] && target >= nums[s]) {
e = p - 1
} else {
s = p + 1
}
} else {
e--
}
}
return false
};
Template generated via Leetmark.