# Is this a reasonable binary search implementation?

import java.util.Arrays;

public class BinarySearch {

// this class should not be instantiated

private BinarySearch() { }

// searches for the integer key in the sorted array a[]
// @param key the search key
// @param a the array of integers, must be sorted in ascending order
// @return index of key in array a[] if present; -1 if not present

public static int rank(int key, int[] a) {
int lo = 0;
int hi = a.length - 1;
while (lo <= hi) {
// key is in a[lo..hi] or not present
int mid = lo + (hi - lo) / 2;
if (key < a[mid]) hi = mid - 1;
else if (key > a[mid]) lo = mid + 1;
else return mid;
}
return 1;

}

// reads in a sequence of integers from the whitelist file, specified as a command line argument. reads in integers from standard input and prints to standard output
// those integers that do not appear in the file.
public static void main(String[] args){

// read the integers from a file
In in = new In(args[0]);

// sort the array
Arrays.sort(whitelist);

// read integer key from standard input; print if not in whitelist
while (!StdIn.isEmpty()) {
if (rank(key, whitelist) == -1)
StdOut.println(key);
}
}

}

– rds
Jun 15 '14 at 10:27
• What's wrong with Arrays.binarySearch ?
– rds
Jun 15 '14 at 10:41
• What is the In class? And what's StdIn and StdOut? I've heard about System.in and such, but never of StdIn. Jun 15 '14 at 11:08
• Considering the lo and hi variables in combination with StdIn and StdOut I'd guess this is part of the Algorithms course by Robert Sedgewick (Princeton) on Coursera. Jun 15 '14 at 22:57

Your implentation can search integers, we expect to search in an array of any comparable objects.

I think you have a bug if the element is not found. It will return 1 instead of -1 / throwing an exception. Add unit tests.

Also, Java is now open source, you can compare your implementation with the one from the JDK (Arrays.binarySearch).

Also, in code style:

• it is recommended to use {} in if block, even if they are one-liner
• /2 will probably automatically be optimized to >>1 as needed Jun 15 '14 at 14:05
• @ratchetfreak That's why I said probably. And now that you triggered my curiosity, I can say that neither ejc nor javac 1.6.0_65 perform this optimization.
– rds
Jun 15 '14 at 19:42
• it may happen at run time though Jun 15 '14 at 19:49
• You are very right, and that's because javac does few optimizations by design anyway. Now, I have to acknowledge I don't know how to look at what the JIT produces.
– rds
Jun 15 '14 at 19:53
• @rds wikis.oracle.com/display/HotSpotInternals/PrintAssembly (the hsdis link on that page is broken, here's the actual link: hg.openjdk.java.net/jdk8u/jdk8u/hotspot/file/tip/src/share/…) Jun 16 '14 at 22:06