The description for this problem states:
There is an integer array
nums
sorted in ascending order (with distinct values).Prior to being passed to your function,
nums
is possibly rotated at an unknown pivot indexk
(1 <= k < nums.length
) such that the resulting array is[nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]
(0-indexed). For example,[0,1,2,4,5,6,7]
might be rotated at pivot index3
and become[4,5,6,7,0,1,2]
.Given the array
nums
after the possible rotation and an integertarget
, return the index oftarget
if it is innums
, or-1
if it is not innums
.You must write an algorithm with
O(log n)
runtime complexity.
For example:
search([4, 5, 6, 7, 0, 1, 2], 0);
// -> 4
search([4, 5, 6, 7, 0, 1, 2], 3);
// -> -1
search([1], 0);
// -> -1
This one is really a hard problem where we have to think of all the cases that can possibly occur.
We'll use binary search, and similar to the previous problem, we'll consider two sorted portions in the array: left and right. Also, as with binary search, we'll have two pointers low
and high
pointing to the 0
th and the last index respectively.
With normal binary search, we search the right portion only when the middle element is less than the target; and search the left portion when the middle element is more than the target. But here, things are different.
If we're in a sorted portion, we'll search the right if:
- the target is greater than the middle element
or
- the target is less than the value that
low
points to.
Otherwise, we'll go left.
Else if we're not in a sorted portion, we'll search the left if:
- the target is less than the middle element
or
- the target is greater than the value that
high
points to.
Otherwise, we'll go right.
Note |
---|
Searching the right refers to updating low to be mid + 1 , and searching the left refers to updating high to be mid - 1 . |
Here is a solution in TypeScript:
function search(nums: number[], target: number): number {
let low = 0;
let high = nums.length - 1;
while (high >= low) {
let mid = Math.floor((high + low) / 2);
if (nums[mid] === target) {
return mid;
}
if (nums[low] <= nums[mid]) {
if (target > nums[mid] || target < nums[low]) {
low = mid + 1;
} else {
high = mid - 1;
}
} else {
if (target < nums[mid] || target > nums[high]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
}
return -1;
};
It might look confusing and hard to wrap your mind around at first, because it is. I find this problem to be one of the most challenging ones in this series so far. It means that it's now time to take a deep breath.
Time and space complexity
The time complexity is as we use binary search, halving the search space with each iteration. The space complexity is because we don't make use of any extra space that proportionally grows with the input size.
Next up, we'll start a chapter on Linked Lists. Until then, happy coding.
Top comments (0)