wood burning stoves 2.0*
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
JavaRanch » Java Forums » Certification » Programmer Certification (SCJP/OCPJP)
Bookmark "binarySearch" Watch "binarySearch" New topic


Mamadou Touré
Ranch Hand

Joined: Dec 27, 2007
Posts: 189

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

SCJP 5 (76%)
SCWCD 5 (86%)
SCBCD 5(70%)
"The greatest glory in living lies not in never falling, but in raising every time we fall.".. Nelson Mandela
Antonio Tercero
Ranch Hand

Joined: Jun 05, 2008
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

Joined: Apr 27, 2008
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.

SCJP 5 (98%) - SCBCD 5 (98%)
Jesper de Jong
Java Cowboy
Saloon Keeper

Joined: Aug 16, 2005
Posts: 14150

Please use code tags when posting code, it makes it much easier to read.

Java Beginners FAQ - JavaRanch SCJP FAQ - The Java Tutorial - Java SE 7 API documentation
Scala Notes - My blog about Scala
I agree. Here's the link: http://aspose.com/file-tools
subject: binarySearch