Day 2 — Rotated sorted array search problem

This is one of problem where you will be get stuck in interview if you don’t know the tricks. But the common approach is also very important.

Pseudo code:

1. Find the pivot element in O(log n).
2. binary search in both side of pivot.

Overall complexity of above approach is O(log n).

but interviewer will ask if you could it in one pass of binary search, actually we are apply the binary search 3 times in above method.

So if we get a little attention, we will observe that the mid element has some property, such as

a. if left side of mid is not sorted, right side must be sorted.
b. if right side of mid is not sorted, left side must be.

Use this property to apply Binary search.