Delphi Clinic C++Builder Gate Training & Consultancy Delphi Notes Weblog Dr.Bob's Webshop
Hubert Klein Ikkink (aka Mr.Haki) - Communications Officer
 Mr.Haki's JBuilder Jar #60
See Also: JBuilder Papers

Revisit of java.util.Arrays
In JBuilder Jar #58 we already have taken a look at the java.lang.Arrays class. We used the sort() method to sort different data types. But the Arrays class contains more useful methods. In this tip we will see the binarySearch() method to search for values in arrays.

Let's begin with the binarySearch() method. We can invoke this method with two parameters, the array in which we want to search and the key to search for. Just as with the sort() method we can use all types of arrays: from integer arrays to Object arrays. We use the same array as in the tip about the sort() method, with the addition of one new member to the team: Rick.

    String[] contributors = new String[] {
      "David", "Micha", "Arjan", "Bob",
      "Hubert", "Barry", "Arnim"
    };
To find for example the String Hubert we can use the following statement:
    int pos = Arrays.binarySearch(contributors, "Hubert");
    if (pos > 0) {
      System.out.println("found key at position " + pos);
    } else {
      System.out.println("key not found");
    }
The binarySearch() method return a integer with the position of the key in the array. If the value of this integer is less than 0, it means the key isn't found.
It is very important to sort the array first, because else the results of the binaraySearch() can be very unpredictable.

We can create our own Comparator class we want to use with the binarySearch() method. Let's create a Comparator class which will be satisfied if the beginning of the value in the array equals the in the key. For example we could use the key Hub to get the position of the first element which starts with this String.

    Comparator startCompare = new Comparator() {
      public int compare(Object o1, Object o2) {
        String s1 = o1.toString();  // array value
        String s2 = o2.toString();  // key (binaraySearch)
        int value = s1.compareTo(s2);
        if (value > 0) {
          int search = s1.indexOf(s2);
          if (search == 0) {
            value = search;
          }
        }
        return value;
      }
    };

It might seem a bit complex, but it isn't. Let's see what happens.

First we cast the two Object parameters to Strings, because we know we are working with a String array.

Next we compare values of the array value and the key value. If both are equal the compareTo() method will return 0, if s1 is less than s2 the return value will be negative, otherwise it is positive. For example comparing Bob with Hub will return a negative value. A positive value means we have gone to far in the array, and missed the value which starts with the key. For example comparing Micha with Hub will return a positive value, and Micha has a higher index in the array, than Hubert, the array value we are looking for. So it means we are close, but not quite there yet.

A positive value means we have to do some further investigation. If the value is positive we try to determine the index of the key value in the array value, which is the statement
  int search = s1.indexOf(s2);.
The indexOf() method returns 0 if the array value starts with the key value, a negative value if the key value cannot be found, and a positive value if the key value is in the array value, but not a the beginning. For example the statement
  int search = "Hubert".indexOf("Hub");
should return 0, and the statement
  int search = "Hubert".indexOf("bert");
should return 2.

In this case we are only interested if the indexOf() method returns 0, so we assign this value to the overall value of the compare() method.

The Comparator classs is finished and we can use it in the code:

    Arrays.sort(contributors, startCompare);
    int pos = Arrays.binarySearch(contributors, "Hub", startCompare);
    if (pos > 0) {
      System.out.println("found key at position " + pos);
    } else {
      System.out.println("key not found");
    }

This results in the following output:

  found key at position 4


This webpage © 1997-2009 by Bob Swart (aka Dr.Bob - www.drbob42.com). All Rights Reserved.