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.