Back to DSA
Search in Rotated Sorted Array
mediumAn ascending sorted array of distinct integers was rotated at some unknown pivot. Given the rotated array and a target value, find the index of the target or return -1 if it is absent. Your solution must run in O(log n) time.
Examples
Example 1:
Input:
nums = [5,6,7,1,2,3,4], target = 3Output:
5Explanation: The value 3 sits at index 5 in the rotated array.
Example 2:
Input:
nums = [5,6,7,1,2,3,4], target = 8Output:
-1Explanation: 8 does not appear in the array.
Hints
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 (nums[mid] == target) return mid;
if (nums[lo] <= nums[mid]) {
if (target >= nums[lo] && target < nums[mid]) hi = mid - 1;
else lo = mid + 1;
} else {
if (target > nums[mid] && target <= nums[hi]) lo = mid + 1;
else hi = mid - 1;
}
}
return -1;
}
}Time complexity
O(log n)Space complexity
O(1)