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

**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
we check the left half of the array, make low = mid-1 but here is the twist, array might be rotated.**arrA[mid]>arrA[low]** - So first we will check
, if true that means first half of the array is in strictly increasing order. so next check if*arrA[mid]>arrA[low]*, if true then we can confirm that element x will exist in first half of the array (so*arrA[mid] > x && arrA[low] <= x*) else array is rotated in right half and element might be in the right half so (*high = mid-1*).*low = mid+1* - If
, if false that means there is rotation in first half of the array . so next check if*arrA[mid]>arrA[low]*, if true then we can confirm that element x will exist in right half of the array (so*arrA[mid] < x && arrA[high] >= x*) else element might be in the first half so (*low = mid+1*).*high = mid-1*

**Complete Code:**

**Output**:

Index of element 5 is 7