aspose file tools*
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
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: 29249
    
139

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: 60057
    
  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: 29249
    
139

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: 320
    
    2
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: 3436
    
  47

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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: array question
 
Similar Threads
Accessing ArrayList by iterator
searching object having certain attribute from arraylist
How to output int array as string
Print all objects
Time complexity for my palindrome detection algorithm?