Win a copy of Design for the Mind this week in the Design forum!

# binarySearch

Mamadou TourĂ©
Ranch Hand
Posts: 189
Hi,

In the K&B book at page 556, its said quote "The insertion point is the place in the collection/array where the element would be inserted to keep the collection/array properly sorted"
And an elemnt is not found by the binarSearch(), a negative value (representing the insertion value) is returned, and the formula for that negative value is ( -(insertion point) -1). Below of the page 557 the followin example is given

import java.util.*;
class SearchObjArray {
public static void main(String [] args) {
String [] sa = {"one", "two", "three", "four"};
Arrays.sort(sa); // #1
for(String s : sa)
System.out.print(s + " ");
System.out.println("\none = "
+ Arrays.binarySearch(sa,"one")); // #2
System.out.println("now reverse sort");
ReSortComparator rs = new ReSortComparator(); // #3
Arrays.sort(sa,rs);
for(String s : sa)
System.out.print(s + " ");
System.out.println("\none = "
+ Arrays.binarySearch(sa,"one")); // #4
System.out.println("one = "
+ Arrays.binarySearch(sa,"one",rs)); // #5
}

static class ReSortComparator
implements Comparator<String> { // #6
public int compare(String a, String b) {
return b.compareTo(a); // #7
}
}
}

I understand that line #4 will fail because we're searching on the sa array without using a comparator while sa is sorted with a comparator. But now my question is why it returns -1 as insertion point ? In my point of view, it should return -3 ie (-(2)-1) because to keep arr sorted properly (two three one four), the "one" should be at the 2nd position, therefore the insertion point is -2-1 = -3 ?

Could someone explain me why -1 ???

Antonio Tercero
Ranch Hand
Posts: 110
It returns -1 because it doesn't know how to find the element.
When it knows how to find an element but it doesn' find the element then binarysearch returns the insertion point.

Ralph Jaus
Ranch Hand
Posts: 342
BinarySearch expects that the array is sorted and since you aren't using a comparator, it expects, that is is sorted in the natural order. Now binarySearch compares "one" with the first element in the array, that is "two". Since "two" is grater than "one" according to the natural order, "one" has to be inserted at the first position, zero, and so binarySearch returns -(0) - 1 = -1.

Jesper de Jong
Java Cowboy
Saloon Keeper
Posts: 15214
36
Please use code tags when posting code, it makes it much easier to read.