package algs12;
import java.util.Arrays;

/* ***********************************************************************
 *  Compilation:  javac StaticSetOfInts.java
 *
 *  Data type to store a set of integers.
 *
 *************************************************************************/

public class StaticSETofInts {
  private final int[] a;
  public StaticSETofInts(int[] keys) {
    // defensive copy
    a = new int[keys.length];
    for (int i = 0; i < keys.length; i++)
      a[i] = keys[i];

    Arrays.sort(a);

    // probably should check that no duplicates
  }

  public boolean contains(int key) {
    return rank(key) != -1;
  }

  // Binary search.
  public int rank(int key) {
    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;
  }
}