Experiments with Dual-Pivot Binary Search.

BinarysearchVSDualPivotBinarysearch.java

/**
 * 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;
  }
}