Description:
There is an integer array nums sorted in ascending order (with distinct values).
Prior to being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]. For example, [0,1,2,4,5,6,7] might be rotated at pivot index 3 and become [4,5,6,7,0,1,2].
Given the array nums after the rotation and an integer target, return the index of target if it is in nums, or -1 if it is not in nums.
You must write an algorithm with O(log n) runtime complexity.
Solution:
Time Complexity : O(log n)
Space Complexity: O(1)
// Binary search
var search = function(nums, target) {
let left = 0, right = nums.length-1;
while(left < right){
const mid = left + Math.floor((right - left)/2)
if(nums[mid]===target) return mid
// When middle element is less than the last element
if (nums[mid] < nums[right]) {
if (target > nums[mid] && target <= nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
// When middle element is greater than the last element
else {
if (target > nums[mid] || target < nums[left]) {
left = mid + 1;
} else {
right = mid;
}
}
}
return left
};
Top comments (1)
I found that solution is very popular and helpful : youtube.com/watch?v=Z76IRo_vV0s