To efficiently search in a rotated sorted array, we use a modified version of binary search. Although the array isn't fully sorted due to the rotation, we can still take advantage of the fact that at least one half of the array (either left or right) is always sorted.
Understanding the Problem
In a regular binary search, we look for the target by checking if it lies in the left or right half, since the array is sorted. In a rotated sorted array, that logic needs adjustment. At every step, we still check the middle element, but also identify which half is sorted, and whether the target lies within that sorted half.
What Cases Can Occur?
- Case 1: The element at mid is the key — In this case, we simply return the index.
- Case 2: The left half is sorted — This means
arr[start] ≤ arr[mid]
. Now:
- If the key lies between
arr[start]
and arr[mid]
, then we discard the right half by moving end = mid - 1
.
- Otherwise, we move
start = mid + 1
to search in the unsorted right half.
- Case 3: The right half is sorted — This means
arr[mid] ≤ arr[end]
. Then:
- If the key lies between
arr[mid]
and arr[end]
, we search the right half by setting start = mid + 1
.
- Otherwise, move
end = mid - 1
to check the left half.
- Case 4: Empty array — If the array is empty, we immediately return
-1
because there's nothing to search.
- Case 5: Single element — We directly compare it with the key. If it matches, return 0; otherwise, return -1.
Why This Works
This approach works in O(log n) time because we effectively discard half the array in every step, just like standard binary search. By checking which half is sorted and narrowing the range intelligently, we find the target if it exists.
It’s a very efficient way to deal with rotated arrays, and works well even for large datasets.