This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.
I was reading the programming questions chapter of a book (something like How to Get Hired at Google). Every so often people complain my coding questions are too hard (they aren't) so I wanted to see what was in the book.
One question was to find the lowest number in a "sorted rotated array". The example is the numbers might appear as 3 4 5 6 7 1 2. You need to find "1". Now obviously a linear search would find it. Really a modified linear search as you can stop as soon as you get to the number 1 since it is lower than it's predecessor. You'd only have to go through the whole array if the lowest number was element 0. I thought about using something binary search related but couldn't think of anything that wasn't overly complex.
The author says you can use binary search. She says "If you compare the first and middle elements (3 and 6), you know that the range is still increasing." I don't see how you know that. In the provided example, that is true. But what if the numbers were 3 1 2 6 7 8? The first and middle elements are the same, but the answer isn't "go right."
The "rotation" splits the array into two halves, with the second half starting at the position of the least number in the array. Assuming there are no duplicates in the array, all numbers in the second half must be lower than all numbers in the first half (instead of rotation, think about it as swapping of the two halves). Therefore, if you take any two indexes and find that the first number is bigger than the second one, the boundary must be between them. This permits the binary search, of course. Lowest number is just to the right of the boundary.
In my opinion, this is a math quiz, not a programming question. Just writing a plain old binary search would be sort of a programming question, I'd say. I'm sure I wouldn't get it right if I had just a pencil and paper, though. I'm pretty grateful for Arrays.binarySearch