This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
The moose likes Programming Diversions and the fly likes array question Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Other » Programming Diversions
Bookmark "array question" Watch "array question" New topic
Author

array question

Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 30130
    
150

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?


[Blog] [JavaRanch FAQ] [How To Ask Questions The Smart Way] [Book Promos]
Blogging on Certs: SCEA Part 1, Part 2 & 3, Core Spring 3, OCAJP, OCPJP beta, TOGAF part 1 and part 2
Bear Bibeault
Author and ninkuma
Marshal

Joined: Jan 10, 2002
Posts: 60794
    
  65

Jeanne Boyarsky wrote:But what if the numbers were 3 1 2 6 7 8?

That doesn't meet the criteria for the array.


[Asking smart questions] [Bear's FrontMan] [About Bear] [Books by Bear]
Jeanne Boyarsky
internet detective
Marshal

Joined: May 26, 2003
Posts: 30130
    
150

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
Ranch Hand

Joined: Mar 08, 2009
Posts: 459
    
    6
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

Joined: Aug 22, 2010
Posts: 3606
    
  60

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
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: array question
 
Similar Threads
searching object having certain attribute from arraylist
Print all objects
How to output int array as string
Accessing ArrayList by iterator
Time complexity for my palindrome detection algorithm?