Last active
September 30, 2017 18:49
-
-
Save andreluisdias/cd17c02daa4a11800f127fa9c24d0f55 to your computer and use it in GitHub Desktop.
Empirical Comparison between manually versus default Binary Search Algorithm
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package examples.algorithms; | |
import java.util.Arrays; | |
import java.util.stream.IntStream; | |
import com.google.common.base.Stopwatch; | |
/** | |
* Binary Search comparison against Java's default Binary Search algorithm. | |
* Manually is better in this case! | |
* | |
* @author Andre Luis de Oliveira Dias (https://about.me/andreluisdias) | |
* @since 30 de set de 2017 | |
*/ | |
public class BinarySearchComparison { // JAVA 8 | |
public static void main(String[] args) { | |
BinarySearchComparison main = new BinarySearchComparison(); | |
// Define data | |
final int[] data = main.getData(); | |
final int elementToSearch = 10000000; | |
// Arrays.binarySearch | |
Stopwatch w1 = Stopwatch.createStarted(); | |
int idx = Arrays.binarySearch(data, elementToSearch); | |
if (idx < 0) idx = -1; | |
w1.stop(); | |
main.printResult(idx, w1, "default"); | |
Stopwatch w2 = Stopwatch.createStarted(); | |
int idxManually = main.binarySearch(data, elementToSearch); | |
w2.stop(); | |
main.printResult(idxManually, w2, "manually"); | |
assert (idx == idxManually); // use JVM hint -ea to turn this on | |
} | |
private int[] getData() { | |
return IntStream.range(1, 10000).toArray(); // [1,30] | |
} | |
private int binarySearch(final int[] data, final int key) { | |
int lo = 0, hi = data.length -1; | |
while (lo <= hi) { | |
int mid = lo + (hi - lo) / 2; | |
if (key < data[mid]) hi = mid -1; | |
else if (key > data[mid]) lo = mid + 1; | |
else return mid; | |
} | |
return -1; | |
} | |
private void printResult(final int idx, final Stopwatch sw, final String prefix) { | |
System.out.println(String.format("(%s) Found idx %s within %s", prefix, idx, sw.toString())); | |
} | |
} |
Added line below to do the final assertion...
if (idx < 0) idx = -1;
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Try it by yourself