01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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;
  }
}