File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes Problem on binarySearch Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "Problem on binarySearch" Watch "Problem on binarySearch" New topic
Author

Problem on binarySearch

Bob CHOI
Ranch Hand

Joined: Nov 10, 2006
Posts: 127
My code below,



it printed out:

2 2
1 not found

if comment line #:

1 1
2 2


What would be the problem that one element couldn't have been found?

Thanks!

[ December 19, 2006: Message edited by: Bob CHOI ]

[ December 19, 2006: Message edited by: Bob CHOI ]

[ December 19, 2006: Message edited by: Bob CHOI ]
[ December 19, 2006: Message edited by: Bob CHOI ]

Hard work rewards
marc weber
Sheriff

Joined: Aug 31, 2004
Posts: 11343

If you check the API documentation for binarySearch, you will see the "list must be sorted into ascending order ... prior to making this call. If it is not sorted, the results are undefined." Note that it's not enough for the list to be sorted -- it must be sorted in ascending order.

To understand why, consider how a binary search works. Basically, it looks at the element in the middle of the list and compares it to the element it's looking for. If that happens to what it's looking for, then it's done. Otherwise, based on the comparison -- and assuming that the list is sorted in ascending order -- it narrows the search to either the first half of the list or the second half of the list. For example, if I'm searching for "75" and the middle element is "50," then 75 (if present at all) must be in the second half of the list, so I can forget about the first half. This process repeats until the element is found or the list runs out of elements.

So if the list is not sorted in ascending order, then binary search results are unpredictable, because the determinations of whether to continue looking in the first half or the second half of the list have no basis.

Because your code uses a very small number of elements (just 1 and 2, added in that order), it's hard to see this pattern. Try adjusting your code to add more elements in different orders before sorting and/or searching.
[ December 19, 2006: Message edited by: marc weber ]

"We're kind of on the level of crossword puzzle writers... And no one ever goes to them and gives them an award." ~Joe Strummer
sscce.org
Bob CHOI
Ranch Hand

Joined: Nov 10, 2006
Posts: 127
Marc, thanks so much for such a nice concrete answer!

i was hurried, hadn't really grasp essence of Collection framework. hopefully do better once without time pressure...
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Problem on binarySearch
 
Similar Threads
SoDuko puzzle
import problem
Reading data from files and other classes
flicker in my program
Declaring an array of objects of a class ???