Smallest Element in Cyclic Sorted Array (Medium) — Practice with Code Visualizer

Imagine you have an array of distinct integers that was originally sorted in strictly ascending order. This array has been cyclically shifted (rotated) an unknown number of times. In a cyclic shift, the last element moves to the front while all other elements shift one position to the right.

For instance, the sorted array [1, 2, 3, 4, 5, 6, 7] could become:

[5, 6, 7, 1, 2, 3, 4] after 3 cyclic shifts
[1, 2, 3, 4, 5, 6, 7] after 7 cyclic shifts (returning to original order)

Given such a cyclically shifted array nums containing distinct elements, your task is to locate and return the smallest element in the array.

Critical Requirement: Your algorithm must achieve a time complexity of O(log n), making a linear scan unacceptable. This constraint hints at the need for a divide-and-conquer approach that exploits the unique structure of the rotated array.

The original sorted array was [1,2,3,4,5]. After 3 cyclic shifts to the right, it transformed into [3,4,5,1,2]. The smallest element is 1.

The original sorted array was [0,1,2,4,5,6,7]. After 4 cyclic shifts, the array became [4,5,6,7,0,1,2]. The smallest element is 0, which marks the rotation pivot point.

This array has been cyclically shifted 4 times (equal to its length), effectively returning it to its original sorted state. The smallest element is 11 at index 0.