1
\$\begingroup\$
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]);
    int[] whitelist = in.readAllInts();

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

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

}
\$\endgroup\$
4
  • 1
    \$\begingroup\$ You should use javadoc comments on your methods. \$\endgroup\$
    – rds
    Jun 15 '14 at 10:27
  • 2
    \$\begingroup\$ What's wrong with Arrays.binarySearch ? \$\endgroup\$
    – rds
    Jun 15 '14 at 10:41
  • \$\begingroup\$ What is the In class? And what's StdIn and StdOut? I've heard about System.in and such, but never of StdIn. \$\endgroup\$ Jun 15 '14 at 11:08
  • \$\begingroup\$ 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. \$\endgroup\$ Jun 15 '14 at 22:57
2
\$\begingroup\$

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
\$\endgroup\$
6
  • 5
    \$\begingroup\$ /2 will probably automatically be optimized to >>1 as needed \$\endgroup\$ Jun 15 '14 at 14:05
  • \$\begingroup\$ @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. \$\endgroup\$
    – rds
    Jun 15 '14 at 19:42
  • 1
    \$\begingroup\$ it may happen at run time though \$\endgroup\$ Jun 15 '14 at 19:49
  • \$\begingroup\$ 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. \$\endgroup\$
    – rds
    Jun 15 '14 at 19:53
  • 1
    \$\begingroup\$ @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/…) \$\endgroup\$ Jun 16 '14 at 22:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy