Search a cyclically sorted array

Imagine we have a sorted array that has been shifted by some amount. Normally we can find the smallest element in the 0 position but now that it’s shifted we want to find an efficient way of finding that lowest element

The brute force method is to iterate through the entire array but that doesn’t take advantage of the semi shorted nature of the array

If we take a random non ending index in the array and compare to the last element in the array what can we assume?

In the following array of [4,5,6,7,8,1,2] we can pick a number (let’s say the mid) 7. We see that 7 > 2 since we see that larger numbers are coming up before smaller numbers the shift is on the left hand side. That means to the left are only numbers larger than the smallest number available. We can eliminate this entire area.

What if we have the other case where we pick an element and its less than the last element? Say array [9, 1, 2, 3, 4, 5] and we pick 2. We see that 2 < 5. We can make an asumption now the smallest value has to be on the left hand side and everything on the right hand side can be eliminated.

Let’s iterate through an entire example to see how we can find the answer

Putting it in code

def bin_search(arr):
    left, right = 0, len(arr) - 1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] > arr[right]:
            left = mid + 1
        else:
            right = mid

    return left