Binary search implementations comparison
Enhancing your benchmark

You might be able to enhance your benchmarks a little bit. Its generally worthwhile to run a test multiple times, as there are often other factors that will affect performance on your machine. This can include other programs running on your computer, available RAM/CPU to your process, etc. I find that I typically want to run something as many times as is reasonable within a given amount of time. 

Once you've done that you'll have to find a reasonable metric to use; I typically go with the mean and also report on the standard error of the mean.

It's also often useful/interesting to compare performance at multiple problem sizes, but you might not be interested in that.

You'll also want to make sure that your benchmark actually takes long enough to run; I find that you at least want to be able to notice it pause to run. If that isn't the case here (I have no idea, I haven't run it) then add a few zeros at the end of numberOfRandoms. Eyeballing it, it looks like it should be fine as-is though.

One other thing to consider is that there is the possibility that you've loaded some of the values from the array into the cache, which can artificially enhance the performance of your second run. My general preferred strategy will look something like this:



repeat n times
    generate massive random array
    run version a
    do a ton of operations on a different massive array to make sure the cache is clean
    run version b
    kill cache again


My Java is rusty, but IIRC some of the newer versions allow higher order functions of some kind, in which case I'd write a function that performs the timing and cache clearing for you and takes a function as a parameter. If your version supports doing that I'd consider adding that as well.

Miscellaneous comments

You calculate the difference between finish and start multiple times in both searchUtilRecursive and searchUtil; just calculate it once at the top and then use that value.

Using a string to represent your mode in search is icky - make an enum.

Why are you sorting the array inside your BinarySearch constructor? Just pass it a sorted array. It's unexpected to me that if I call BinarySearch on an array that it will first sort it.

On that note, BinarySearch is weird to have as a class; I'd rather have your search functions be static functions (when do I ever want an instance of a BinarySearch?).

I really dislike that you have statements on the same lines as your if and else - these are small enough functions that it doesn't hurt you to put them on multiple lines, and its way more readable that way.