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.

Rotated Sorted Array

Rotated Sorted Array

Approach:

Naive Approach: Do the linear scan and find the element in O(n) time

Better Approach:

  • 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).

Complete Code:


Output:

Index of element 5 is 7

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

%d bloggers like this: