min in rotated array
November 26, 2023 · 231 words · 2 min read · tech, programming
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,4,4,5,6,7] might become:
[4,5,6,7,0,1,4] if it was rotated 4 times. [0,1,4,4,5,6,7] if it was rotated 7 times.
solution
On first look, it is easy to observe this should only be O(n). But, since it is a sorted array, ideally we should be able to do this in O(log n).
if we imagine the array to be circular list joined at the highest and lowest value. we can select any to adjacent values (call them l and r), it is provable that apart from the exact join, l<r.
if we find a for these, the middle point(m), it would be the diametrically opposite value. Now, with this, there are 3 possible cases.
- middle value is less than the right value. This means, the minimum is on the left side. so we make
r=m - middle value is greater than the right value. This means, the minimum is on the right side. so we make
l=m - middle value is equal to the right value. we don’t know which side. so we make
r=r-1. This means that, the true O() value is still O(n) because in the worst case where all elements are the same, we will have to traverse the entire array. but, in every other case it is O(log n).
Frodo: “It’s a pity Bilbo didn’t kill Gollum when he had the chance.”
Gandalf: “Pity? It’s a pity that stayed Bilbo’s hand. Many that live deserve death. Some that die deserve life. Can you give it to them, Frodo? Do not be too eager to deal out death in judgment. Even the very wise cannot see all ends. My heart tells me that Gollum has some part to play in it, for good or evil, before this is over. The pity of Bilbo may rule the fate of many.”
Frodo: “I wish the Ring had never come to me. I wish none of this had happened.”
Gandalf: “So do all who live to see such times, but that is not for them to decide. All we have to decide is what to do with the time that is given to us. There are other forces at work in this world, Frodo, besides that of evil. Bilbo was meant to find the Ring, in which case you were also meant to have it. And that is an encouraging thought.” ― J.R.R. Tolkien, The Fellowship of the Ring