• Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

BinarySearch

 
Abhi vijay
Ranch Hand
Posts: 509
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Source: K&B



Line 1 is printing -4, but shouldnt it be -3??
 
Ankit Garg
Sheriff
Posts: 9521
22
Android Google Web Toolkit Hibernate IntelliJ IDE Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No, -4 is correct (Hint: we didn't use comparator while searching)...
 
Punit Singh
Ranch Hand
Posts: 952
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
It is undefined behavior here, so you cannot say anything here.
 
Abhi vijay
Ranch Hand
Posts: 509
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator


If you want calculation index, then run this.
 
Ankit Garg
Sheriff
Posts: 9521
22
Android Google Web Toolkit Hibernate IntelliJ IDE Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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: 9521
22
Android Google Web Toolkit Hibernate IntelliJ IDE Java Spring
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Arrays.binarySearch(a, new MyComparator());


What are you searching here?
 
Yuan Du
Ranch Hand
Posts: 34
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
oh, sorry, i meant one element of object array 'a'.

eg.Arrays.binarySearch(a, a[0]);
 
Punit Singh
Ranch Hand
Posts: 952
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, thank you Punit.
I got it.


Yuan
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic