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.

Rotated Sorted Array
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:

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