my dog learned polymorphism*
The moose likes Programmer Certification (SCJP/OCPJP) and the fly likes BinarySearch 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 » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "BinarySearch" Watch "BinarySearch" New topic
Author

BinarySearch

Abhi vijay
Ranch Hand

Joined: Sep 16, 2008
Posts: 509
Source: K&B



Line 1 is printing -4, but shouldnt it be -3??
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

No, -4 is correct (Hint: we didn't use comparator while searching)...


SCJP 6 | SCWCD 5 | Javaranch SCJP FAQ | SCWCD Links
Punit Singh
Ranch Hand

Joined: Oct 16, 2008
Posts: 952
It is undefined behavior here, so you cannot say anything here.


SCJP 6
Abhi vijay
Ranch Hand

Joined: Sep 16, 2008
Posts: 509
Ankit Garg wrote:No, -4 is correct (Hint: we didn't use comparator while searching)...


Yes, I know we havent used Comparator. But then how is it calculating the insertion point??? :?:
Punit Singh
Ranch Hand

Joined: Oct 16, 2008
Posts: 952


If you want calculation index, then run this.
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

As punit said, and as the documentation says, the result is undefined. Actually it uses binary search algorithm i.e. breaking the array into half and then matching the element, so it will first match pen with the middle element i.e. marble in this case. Since it will find pen to be greater than marble, so it will move forward and break the remaining array into half but since there is only one element so it will match pen with the last element i.e. map and will find it even greater than that so it will think that pen must be the last element i.e. 4th element or element at index 3. So it will return - (index + 1) i.e. - (3 + 1) i.e. -4...
Abhi vijay
Ranch Hand

Joined: Sep 16, 2008
Posts: 509
Thanks, But I know how to calculate insertion point when comparator is used. But didnt know how it is done without comparator. I think Ankit has explained it.
Ankit Garg
Sheriff

Joined: Aug 03, 2008
Posts: 9291
    
  17

Abhi vijay wrote:Thanks, But I know how to calculate insertion point when comparator is used. But didnt know how it is done without comparator. I think Ankit has explained it.


It is not about comparator. I just explained the binary search algorithm here and how in this case it will lead to wrong result since we didn't use the comparator while searching . The binary search algorithm is the same whether you use comparator or not...
Yuan Du
Ranch Hand

Joined: Nov 20, 2008
Posts: 34
Hi everyone,

This is from KB book page 558
When solving searching and sorting questions, two big gotchas are:
1. Searching an array or collection that hasn’t been sorted.
2. Using a Comparator in either the sort or the search,
but not both

I don't understand the second point, why we can't use a comparator for sorting and searing.

Thank you very much!

Yuan
Punit Singh
Ranch Hand

Joined: Oct 16, 2008
Posts: 952
Second point is saying, if you sort a list using Comparator, then you must search that list using Comparator by passing Comparator as third argument to binarySearch(), otherwise result will be undefined.
Yuan Du
Ranch Hand

Joined: Nov 20, 2008
Posts: 34
Ok Punit.
You mean i should use the method "public static <T> int binarySearch(T[] a, T key, Comparator<? super T> c)",
but i can not code it in two statements
like


because the sequence of the object[] won't be changed after the first statement, am i right?

Thank you!

Yuan
Punit Singh
Ranch Hand

Joined: Oct 16, 2008
Posts: 952
Arrays.binarySearch(a, new MyComparator());


What are you searching here?
Yuan Du
Ranch Hand

Joined: Nov 20, 2008
Posts: 34
oh, sorry, i meant one element of object array 'a'.

eg.Arrays.binarySearch(a, a[0]);
Punit Singh
Ranch Hand

Joined: Oct 16, 2008
Posts: 952
If you have use new MyComparator() is sorting:



then you must use new MyComparator() is searching also,



Otherwise you will get answer undefined. It may happen MyComparator sorted data in reverse order, and you did not pass MyComparator in binarySearch, then binarySearch will search data in natural order instead of reverse order and you will get undefined result.

Yuan Du
Ranch Hand

Joined: Nov 20, 2008
Posts: 34
Ok, thank you Punit.
I got it.


Yuan
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
 
subject: BinarySearch
 
Similar Threads
Arrays java.util collections class - binarySearch() method
Error in Sun Certified Programmer for Java 6 Study Guide
Why doesn't the subclass variable hide it?
Arrays sort doubt.
need help with Arrays.sort() and compareTo()