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>