Understanding searching in a sorted rotated array

Binary search to find a target value in a sorted array is an exponentially fast algorithm that only works on sorted arrays. However, we can also search for a target item in a sorted rotated array using the same underlying principle as binary search, exploiting its semi-sorted nature. As we will see later, this semi-sorted structure allows us to discard one half of the search space in each iteration until we find the target value.

A sorted rotated array is one where a sorted array is rotated in either direction by a certain number of times. While the array is no longer sorted, we can still efficiently search for items in such arrays using the sorted rotated search algorithm.

The sorted rotated search algorithm

Consider a sorted array arr that is rotated an unknown number of times in either (left or right) direction, and we need to find if a value target exists in the array.

Every sorted rotated array of size n has a pivot index p where arr[p] is the minimum item in the array.