Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand.
(i.e., [0,1,2,4,5,6,7] might become [4,5,6,7,0,1,2]).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
Your algorithm’s runtime complexity must be in the order of O(log n).
Example 1:
Input: nums = [4,5,6,7,0,1,2], target = 0
Output: 4
Example 2:
Input: nums = [4,5,6,7,0,1,2], target = 3
Output: -1
[code lang="java"]
class Solution {
public int search(int[] nums, int target) {
}
}
[code]
Idea – 1
There are no duplicates. So, after rotation the single sorted array breaks into two sorted arrays separated by a break. We do modified binary search, deciding to go left or right but we need to consider cases when mid is to the left or to the right of the break. Time complexity is
and space is 
.
[code lang="java"]
class Solution {
public int search(int[] nums, int target) {
int lo = 0, hi = nums.length-1;
while(lo <= hi)
{
int mid = lo + (hi-lo)/2;
if(target == nums[mid])
{
return mid;
}
else if(nums[mid] > nums[hi]) // mid is to the left of break
{
if(target >= nums[lo] && target < nums[mid]) // target is between lo and mid
{
// go left
hi = mid-1;
}
else
{
// go right
lo = mid+1;
}
}
else // mid is to the right of break;
{
if(target > nums[mid] && target <= nums[hi]) // target is between mid and hi
{
// go right
lo = mid+1;
}
else
{
// go left
hi = mid-1;
}
}
}
return -1;
}
}
[code]
Runtime: 0 ms, faster than 100.00% of Java online submissions for Search in Rotated Sorted Array.
Memory Usage: 38.9 MB, less than 75.56% of Java online submissions for Search in Rotated Sorted Array.
programmingpuzzles 