Search an element in a sorted and rotated Array

  • For a sorted (in increasing order) and rotated array, the pivot element is the only element for which the next element to it is smaller than it.
  • Using binary search based on the above idea, pivot can be found.
  • It can be observed that for a search space of indices in range [l, r] where the middle index is mid,
  • If rotation has happened in the left half, then obviously the element at l will be greater than the one at mid.
  • Otherwise the left half will be sorted but the element at mid will be greater than the one at r.
  • After the pivot is found divide the array into two sub-arrays.
  • Now the individual sub-arrays are sorted so the element can be searched using Binary Search.
Index of the element is : 8

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store