**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

**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..-**

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

__________________________________________________

### Like this:

Like Loading...

*Related*