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}