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.
Constraints
Approach
Links
Examples
Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 0
Output: true
Input: nums = [2, 5, 6, 0, 0, 1, 2], target = 3
Output: false
Solutions
/**
* Time complexity : O(n)
* Space complexity : O(1)
*/
class Solution {
public boolean search(int[] nums, int target) {
for(int i = 0; i < nums.length; i++) {
if(nums[i] == target) return true;
}
return false;
}
}
/**
* Time complexity : O(logN)
* Space complexity : O(1)
*/
class Solution {
public boolean search(int[] nums, int target) {
int left = 0, right = nums.length-1;
while(left <= right) {
int mid = left + (right-left)/2;
if(target == nums[mid]) return true;
if(nums[left] < nums[mid]) {
if(target >= nums[left] && target <= nums[mid]) {
right = mid - 1;
} else {
left = mid + 1;
}
} else if(nums[left] > nums[mid]) {
if(target >= nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid - 1;
}
} else {
left++;
}
}
return false;
}
}
Follow up
Would this affect the run-time complexity? How and why?