Binary searching an array

Since JDK1.2, the utility class Arrays in the java.util package provides useful
array manipulation methods such as fill, binary search and sort. Before using
the binary search method, you should make sure the array is sorted. Binary searching
on an unsorted array gives undefined results. The binarySearch function is defined
for arrays of type byte[], char[], double[], float[], int[], long[], object[].

You pass the method the key you want to lookup. It returns with either
the index, if the key is found, or the insertion point defined as
(-return value)-1, as the index where the value should be inserted to keep
the array sorted.
Following example demonstrates the use:

import java.util.Arrays;
 
public class Main
{
   public static void main(String args[]) {
      int values[] = { 5, 74, 23, 99, 6, 0, -2, -60 };
 
      System.out.println("Unsorted array:");
      printArray(values);
 
      Arrays.sort(values);
 
      System.out.println("Sorted array:");
      printArray(values);
 
      int v1 = 6;
      int v2 = 34;
      int r1 = Arrays.binarySearch(values, v1);
      int r2 = Arrays.binarySearch(values, v2);
 
      printResult(v1, r1);
      printResult(v2, r2);
   }
 
   public static void printArray(int []values) {
      for (int i=0; i<values.length; i++) {
         System.out.print(values[i] + " ");
      }
      System.out.println();
      System.out.println();
   }
 
   public static void printResult(int value, int index) {
      if (index < 0) {
         int ip = -index - 1;
         System.out.println(value + " not found.  Insertion point = " + ip);
      }
      else {
         System.out.println(value + " found at index " + index);
      }
   }
}

outputs:

Unsorted array:
5 74 23 99 6 0 -2 -60 
 
Sorted array:
-60 -2 0 5 6 23 74 99 
 
6 found at index 4
34 not found.  Insertion point = 6

You can just as easily binary search on user-defined objects. The only catch
is that you will have to define a comparator to tell the method whether object
A is less than, equal or bigger than object B.
Here’s an example:
RedColorComparator is introduced, a Comparator that only takes into account the red value of
the RGB value.

import java.util.Comparator;
import java.util.Arrays;
import java.awt.Color;
 
public class Main
{
   public static void main(String []args) {
      Color colArr[] = { new Color(43, 100, 100), new Color(170, 59, 255),
                            new Color(0, 0, 0), new Color(220, 220, 220),
                            new Color(10, 255, 255), new Color(255, 0, 0) };
 
      System.out.println("Unsorted array:");
      printArray(colArr);
      Arrays.sort(colArr, new RedColorComparator());
      System.out.println("Sorted array:");
      printArray(colArr);
 
      Color v1 = new Color(220, 220, 220);
      Color v2 = new Color(11, 0, 0);
      int r1 = Arrays.binarySearch(colArr, v1, new RedColorComparator());
      int r2 = Arrays.binarySearch(colArr, v2, new RedColorComparator());
  
      printResult(v1, r1);
      printResult(v2, r2);
   }
 
   public static void printArray(Color colArr[]) {
      for (int i=0; i<colArr.length; i++) 
         System.out.println(colArr[i]);
      System.out.println();
   }
 
   public static void printResult(Color value, int index) {
      if (index < 0) {
         int ip = -index - 1;
         System.out.println(value + " not found.  Insertion point = " + ip);
      }
      else {
         System.out.println(value + " found at index " + index);
      }
   }
}
 
class RedColorComparator implements Comparator
{
   public int compare(Object o1, Object o2) {
      int red1 = ((Color) o1).getRed();
      int red2 = ((Color) o2).getRed();
      return (new Integer(red1)).compareTo(new Integer(red2));
   } 
}

outputs:

Unsorted array:
java.awt.Color[r=43,g=100,b=100]
java.awt.Color[r=170,g=59,b=255]
java.awt.Color[r=0,g=0,b=0]
java.awt.Color[r=220,g=220,b=220]
java.awt.Color[r=10,g=255,b=255]
java.awt.Color[r=255,g=0,b=0]
 
Sorted array:
java.awt.Color[r=0,g=0,b=0]
java.awt.Color[r=10,g=255,b=255]
java.awt.Color[r=43,g=100,b=100]
java.awt.Color[r=170,g=59,b=255]
java.awt.Color[r=220,g=220,b=220]
java.awt.Color[r=255,g=0,b=0]
 
java.awt.Color[r=220,g=220,b=220] found at index 4
java.awt.Color[r=11,g=0,b=0] not found.  Insertion point = 2