001package algs12;
002import java.util.Arrays;
003
004/* ***********************************************************************
005 *  Compilation:  javac StaticSetOfInts.java
006 *
007 *  Data type to store a set of integers.
008 *
009 *************************************************************************/
010
011public class StaticSETofInts {
012        private final int[] a;
013        public StaticSETofInts(int[] keys) {
014                // defensive copy
015                a = new int[keys.length];
016                for (int i = 0; i < keys.length; i++)
017                        a[i] = keys[i];
018
019                Arrays.sort(a);
020
021                // probably should check that no duplicates
022        }
023
024        public boolean contains(int key) {
025                return rank(key) != -1;
026        }
027
028        // Binary search.
029        public int rank(int key) {
030                int lo = 0;
031                int hi = a.length - 1;
032                while (lo <= hi) {
033                        // key is in a[lo..hi] or not present.
034                        int mid = lo + (hi - lo) / 2;
035                        if      (key < a[mid]) hi = mid - 1;
036                        else if (key > a[mid]) lo = mid + 1;
037                        else return mid;
038                }
039                return -1;
040        }
041}