Mastery Points
0
Search in Rotated Array in dsa
Context & Logic
Searching in a sorted but rotated array requires identifying which half of the array is sorted at each step.
Example
function search(nums, target) {
let low = 0, high = nums.length - 1;
while (low <= high) {
let mid = Math.floor((low + high) / 2);
if (nums[mid] === target) return mid;
if (nums[low] <= nums[mid]) {
if (target >= nums[low] && target < nums[mid]) high = mid - 1;
else low = mid + 1;
} else {
if (target > nums[mid] && target <= nums[high]) low = mid + 1;
else high = mid - 1;
}
}
return -1;
}Step-by-Step Logic
1
Check if the left half [low...mid] is sorted.
2
If sorted, check if target lies within this range.
3
Otherwise, search the right half.
Complexity Metrics
Time Efficiency
O(log n)
Memory Footprint
O(1)