Searching In Shifted Sorted Array

This question has been asked to me in more than 3 tech interviews out if 12-14+ interviews till date. This is a very popular question, it is a very easy and straight forward problem statement, therefore the assumptions and confusions faced are really less or none. Basically, you have been given a sorted array which has been rotated by a few turns (refer to the above diagram), you need to find if an element is present in the rotated array.

The naive approach would be to traverse the array and perform a linear search. But what the interviewer is looking for is a sub-optimal runtime algorithm. Also, don't try to sort the array again because it was already sorted.

The answer is binary search. Note that the array is still sorted, except the starting part is shifted by some scalar value (less than the length of the array).

There are two ways of solving this problem.

• First Option: Try to calculate by how much the array was rotated using binary search, then use that knowledge along with modulus trick to search for the target element. This is a two-pass algorithm.
  Get the Python code here.
• Second Option: Note that if we apply binary search to this array, one side will be sorted another side will not be sorted. To the sorted side, you can search if the target element is present or not by checking the range, if it is present then do continue searching on that side else search on the other side. If this low...mid was not sorted then check mid...high, which must be sorted, then apply the same logic and repeat iteratively. This is a single pass binary search solution.
  Get the Python code here.