Search an Element in a Rotated Sorted Array
Input: Rotated Sorted Array.
What is Rotated Sorted Array.
A sorted array is rotated around some pivot element. See the Example Below, array is rotated after 6.
Naive Approach: Do the linear scan and find the element in O(n) time
- Since array is still sorted we can use binary search to find the element in O(logn) but we cannot apply normal binary search technique since array is rotated.
- Say array is arrA and element needs to be searched is ‘x’.
- Normally when arrA[mid]>arrA[low] we check the left half of the array, make low = mid-1 but here is the twist, array might be rotated.
- So first we will check arrA[mid]>arrA[low], if true that means first half of the array is in strictly increasing order. so next check if arrA[mid] > x && arrA[low] <= x, if true then we can confirm that element x will exist in first half of the array (so high = mid-1) else array is rotated in right half and element might be in the right half so (low = mid+1).
- If arrA[mid]>arrA[low], if false that means there is rotation in first half of the array . so next check if arrA[mid] < x && arrA[high] >= x, if true then we can confirm that element x will exist in right half of the array (so low = mid+1) else element might be in the first half so (high = mid-1).
Index of element 5 is 7