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

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