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 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...
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.
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.
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.