public final class Binary { public static int search (final int v, final int[] data) { return search (v, data, 0, data.length); } public static int search (final int v, final int[] data, final int last) { return search (v, data, 0, last); } // Search everything from 'first' to 'last-1' (inclusive) public static int search (final int v, final int[] data, final int first, final int last) { assert 0<=first && first<=data.length; assert 0<=last && last<=data.length; int low = first, high = last-1; while (low <= high) { final int mid = (low+high)>>>1; // works even when + overflows assert low<=mid; assert mid<=high; if (data[mid] == v) { return mid; // EXIT; v found } else if (data[mid] < v) { System.out.printf ("data[%d]=%d is too low%n", mid, data[mid]); // Everything from 'low' to 'mid' is excluded. assert low < mid+1; low = mid+1; } else { assert data[mid] > v; System.out.printf ("data[%d]=%d is too high%n", mid, data[mid]); // Everything from 'mid' to 'high' is excluded. assert mid-1 < high; high = mid-1; } } return -1; // v not found } public static void main (final String [] args) { final int [] data = new int [args.length-1]; final int v = Integer.parseInt (args[0]); int n = 0; for (int i=1; i<args.length; i++) { try { data[n++] = Integer.parseInt (args[i]); } catch (NumberFormatException ex) { ex.printStackTrace (System.err); } } System.out.printf ("Searching for %d in %s%n", n, java.util.Arrays.toString(data)); final int i = search (v, data, n); if (i==-1) { System.out.printf ("%d not found%n", v); } else { System.out.printf ("%d found at index %d%n", v, i); } } }