This week's book giveaway is in the Design forum.We're giving away four copies of Design for the Mind and have Victor S. Yocco on-line!See this thread for details.
Win a copy of Design for the Mind this week in the Design forum!

# BinarySearch

Abhi vijay
Ranch Hand
Posts: 509
Source: K&B

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

Ankit Garg
Sheriff
Posts: 9519
22
No, -4 is correct (Hint: we didn't use comparator while searching)...

Punit Singh
Ranch Hand
Posts: 952
It is undefined behavior here, so you cannot say anything here.

Abhi vijay
Ranch Hand
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
Posts: 952

If you want calculation index, then run this.

Ankit Garg
Sheriff
Posts: 9519
22
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
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
Posts: 9519
22
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
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
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
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
Posts: 952
Arrays.binarySearch(a, new MyComparator());

What are you searching here?

Yuan Du
Ranch Hand
Posts: 34
oh, sorry, i meant one element of object array 'a'.

eg.Arrays.binarySearch(a, a[0]);

Punit Singh
Ranch Hand
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
Posts: 34
Ok, thank you Punit.
I got it.

Yuan