Win a copy of The Java Performance Companion this week in the Performance forum!

# array question

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34670
367
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."

Am I missing something?

Bear Bibeault
Author and ninkuma
Marshal
Posts: 64967
86
Jeanne Boyarsky wrote:But what if the numbers were 3 1 2 6 7 8?

That doesn't meet the criteria for the array.

Jeanne Boyarsky
author & internet detective
Marshal
Posts: 34670
367
Bear Bibeault wrote:
Jeanne Boyarsky wrote:But what if the numbers were 3 1 2 6 7 8?

That doesn't meet the criteria for the array.

Oh, right. Tricky! I can longer come up with a counter example that does meet the conditions so the answer makes sense now.

Piet Souris
Rancher
Posts: 1296
28
A quicky, because the champions legue final between Bayern and Dortmund is about to begin:

you can find the smallest number of a 'sorted rotated array' even faster still: take element 0.

Now, for a 'rotated sorted array' things would be a little different... ;)) (can't get my smilies to work)

Greetings,
Piet

Martin Vajsar
Sheriff
Posts: 3752
62
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