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

This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.

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

This site uses Akismet to reduce spam. Learn how your comment data is processed.