Java Tutorial/Collections/Search

Binary search

   <source lang="java">

import java.util.Arrays; import java.util.Random; public class MainClass {

 private static int[] data = new int[10]; // create space for array
 public static void main(String[] args) {
   Random generator = new Random();
   for (int i = 0; i < 10; i++)
     data[i] = 10 + generator.nextInt(90);
   Arrays.sort(data);
   System.out.println(binarySearch(3));
 }
 public static int binarySearch(int searchElement) {
   int low = 0;
   int high = data.length - 1;
   int middle = (low + high + 1) / 2;
   int location = -1;
   do {
     System.out.print(remainingElements(low, high));
     for (int i = 0; i < middle; i++)
       System.out.print("   ");
     System.out.println(" * ");
     if (searchElement == data[middle])
       location = middle;
     else if (searchElement < data[middle])
       high = middle - 1;
     else
       low = middle + 1;
     middle = (low + high + 1) / 2;
   } while ((low <= high) && (location == -1));
   return location;
 }
 public static String remainingElements(int low, int high) {
   StringBuffer temporary = new StringBuffer();
   for (int i = 0; i < low; i++)
     temporary.append("   ");
   for (int i = low; i <= high; i++)
     temporary.append(data[i] + " ");
   temporary.append("\n");
   return temporary.toString();
 }

}</source>

16 20 31 58 64 75 83 85 86 96 
                * 
16 20 31 58 64 
       * 
16 20 
    * 
16 
 * 
-1

Recursive Binary Search Implementation in Java

   <source lang="java">

public class Main {

 public static final int NOT_FOUND = -1;
 public static int binarySearch(Comparable[] a, Comparable x) {
   return binarySearch(a, x, 0, a.length - 1);
 }
 private static int binarySearch(Comparable[] a, Comparable x, int low, int high) {
   if (low > high)
     return NOT_FOUND;
   int mid = (low + high) / 2;
   if (a[mid].rupareTo(x) < 0)
     return binarySearch(a, x, mid + 1, high);
   else if (a[mid].rupareTo(x) > 0)
     return binarySearch(a, x, low, mid - 1);
   else
     return mid;
 }
 public static void main(String[] args) {
   int SIZE = 8;
   Comparable[] a = new Integer[SIZE];
   for (int i = 0; i < SIZE; i++)
     a[i] = new Integer(i * 2);
   for (int i = 0; i < SIZE * 2; i++)
     System.out.println("Found " + i + " at " + binarySearch(a, new Integer(i)));
 }

}</source>