Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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 ele­ment. See the Exam­ple Below, array is rotated after 6.

Rotated Sorted Array

Rotated Sorted Array

Approach:

Naive Approach: Do the lin­ear scan and find the ele­ment in O(n) time

Bet­ter Approach:

  • Since array is still sorted we can use binary search to find the ele­ment in O(logn) but we can­not apply nor­mal binary search tech­nique since array is rotated.
  • Say array is arrA[] and ele­ment needs to be searched is ‘x’.
  • Nor­mally 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 increas­ing order. so next check if arrA[mid] > x && arrA[low] <= x, if true then we can con­firm that ele­ment x will exist in first half of the array (so high = mid-1) else array is rotated in right half and ele­ment might be in the right half so (low = mid+1).
  • If arrA[mid]>arrA[low], if false that means there is rota­tion in first half of the array . so next check if arrA[mid] < x && arrA[high] >= x, if true then we can con­firm that ele­ment x will exist in right half of the array (so low = mid+1) else ele­ment might be in the first half so (high = mid-1).

Com­plete Code:


Out­put:

Index of element 5 is 7

You may also like...