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

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:

 public class RotatedSortedArray { public static void main(String args[]) { int a[] = { 10, 11, 12, 1, 2, 3, 4, 5, 6, 7, 8 }; RotatedSortedArray r = new RotatedSortedArray(); System.out.println("Index of element 5 is " + r.findElement(a, 5)); } public int findElement(int[] arrA, int element) { int low = 0; int high = arrA.length – 1; while (low <= high) { int mid = (low + high) / 2; if (arrA[mid] == element) { return mid; } if (arrA[mid] >= arrA[low]) { if (arrA[mid] > element && arrA[low] <= element) { //means first half is in strictly increasing order high = mid – 1; } else { // if you are here means array has rotation in the second half // of the array low = mid + 1; } } else { //if you are here means array has rotation in the first half // of the array if (arrA[mid] < element && arrA[high] >= element) { // means second half is in strictly increasing order low = mid + 1; } else { high = mid – 1; } } } return –1; } }

Output:

```Index of element 5 is 7
```