Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
Experiments with Dual-Pivot Binary Search.
/**
* Experiments with Dual-Pivot Binary Search.
* Written by Vladimir Kostyukov, http://vkostyukov.ru
*/
package dpbs;
import org.openjdk.jmh.annotations.GenerateMicroBenchmark;
import org.openjdk.jmh.annotations.State;
import org.openjdk.jmh.annotations.Scope;
import org.openjdk.jmh.annotations.BenchmarkMode;
import org.openjdk.jmh.annotations.Mode;
import org.openjdk.jmh.runner.Runner;
import org.openjdk.jmh.runner.RunnerException;
import org.openjdk.jmh.runner.options.Options;
import org.openjdk.jmh.runner.options.OptionsBuilder;
import org.openjdk.jmh.annotations.OutputTimeUnit;
import java.util.concurrent.TimeUnit;
@State(Scope.Thread)
@BenchmarkMode(Mode.AverageTime)
@OutputTimeUnit(TimeUnit.NANOSECONDS)
public class DPBS {
private int n = 100000000;
private int data[] = new int[n];
private int k = new java.util.Random().nextInt(n);
public DPBS() {
// data init
for (int i = 0; i < n; i++) {
data[i] = i;
}
}
@GenerateMicroBenchmark
public int benchmarkBS() {
return binarysearch(data, k);
}
@GenerateMicroBenchmark
public int benchmarkDPBS() {
return dualPivotBinarysearch(data, k);
}
public static int binarysearch(int a[], int k) {
return binarysearch(a, k, 0, a.length);
}
public static int binarysearch(int a[], int k, int lo, int hi) {
if (lo == hi) return -1;
int p = lo + (hi - lo) / 2;
if (k < a[p]) {
return binarysearch(a, k, lo, p);
} else if (k > a[p]) {
return binarysearch(a, k, p + 1, hi);
}
return p;
}
public static int dualPivotBinarysearch(int a[], int k) {
return dualPivotBinarysearch(a, k, 0, a.length);
}
public static int dualPivotBinarysearch(int a[], int k, int lo, int hi) {
if (lo == hi) return -1;
int p = lo + (hi - lo) / 3;
int q = lo + 2 * (hi - lo) / 3;
if (k < a[p]) {
return dualPivotBinarysearch(a, k, lo, p);
} else if (k > a[p] && k < a[q]) {
return dualPivotBinarysearch(a, k, p + 1, q);
} else if (k > a[q]) {
return dualPivotBinarysearch(a, k, q + 1, hi);
}
return (k == a[p]) ? p : q;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment