Medium Searching
Binary Search on a Rotated Array
Receives an array of integers that was sorted in ascending order and then rotated at an unknown pivot (e.g. [4,5,6,7,0,1,2]), plus a target value. At each step it looks at the middle element and first figures out which half of the current range — left or right — is still contiguously sorted by comparing the boundary values; then it checks whether the target falls inside that sorted half's value range to decide whether to keep searching there or move to the other half, halving the range each step. Returns the index (position) where the target is found, or -1 if it is not present.
Visualization
- Input
- Result
Algorithm code
// Search in Rotated Sorted Array — a single pure function. Receives an
// ascending array that was rotated at an unknown pivot, and a target,
// returns the index of the target, or -1 if it is not present.
/**
* @param {number[]} arr - ascending array rotated at an unknown pivot
* @param {number} target - value to find
* @returns {number} index of target, or -1 if absent
*/
export function searchRotated(arr, target) {
let lo = 0;
let hi = arr.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (arr[mid] === target) {
return mid;
}
if (arr[lo] <= arr[mid]) {
if (arr[lo] <= target && target < arr[mid]) {
hi = mid - 1;
} else {
lo = mid + 1;
}
} else {
if (arr[mid] < target && target <= arr[hi]) {
lo = mid + 1;
} else {
hi = mid - 1;
}
}
}
return -1;
}FUNCTION searchRotated(arr, target):
lo ← 0
hi ← length(arr) - 1
WHILE lo ≤ hi:
mid ← floor((lo + hi) / 2)
IF arr[mid] = target:
RETURN mid
IF arr[lo] ≤ arr[mid]:
IF arr[lo] ≤ target AND target < arr[mid]:
hi ← mid - 1
ELSE:
lo ← mid + 1
ELSE:
IF arr[mid] < target AND target ≤ arr[hi]:
lo ← mid + 1
ELSE:
hi ← mid - 1
RETURN -1