title: Removing duplicates from a sorted int[] using binarysearch
body: <p>I have a rather large int[] which is sorted using <code>Arrays.sort()</code> .. I need to remove the duplicate elements from the array.</p>
  
  <p>This question originates from sedgewick's Algorithms book 1.1.28 </p>
  
  <blockquote>
    <p>1.1.28 Remove duplicates. Modify the test client in BinarySearch to remove any du- plicate keys in the whitelist after the sort.</p>
  </blockquote>
  
  <p>I tried to create a noDupes() method which takes in an int[] and returns an int[] with duplicates removed</p>
  
  <p>The rank() methods are from sedgewick's code.which does the binary search</p>
  
  <pre><code>public static int[] noDupes(int[] a){
      Arrays.sort(a);
      int maxval= a[a.length-1];
      int[] nodupes = new int[maxval];
      int i=0;
      for(int j=0;j&lt;a.length;j++){
          int rnk = rank(a[j],nodupes);
          System.out.println(a[j]+" rank="+rnk);
          if (rnk &lt; 0){
              System.out.println(a[j]+" is not dupe");
              nodupes[i] = a[j];
              i++;
          }
      }
  
      return nodupes;
  }
  public static int rank(int key,int[] a){
      return rank(key,a,0,a.length-1);
  }
  
  public static int rank(int key,int[] a,int lo,int hi){
      if(lo &gt; hi) return -1;
      int mid = lo+(hi-lo)/2;
  
      if(key &lt; a[mid])return rank(key,a,0,mid-1);
      else if(key &gt; a[mid])return rank(key,a,mid+1,hi);
      else return mid;
  }
  </code></pre>
  
  <p>When I ran this with a sample array </p>
  
  <pre><code>int[] a =new int[]{2,2,2,3,4,4,5,6};
  int[] ret = noDupes(a);
  </code></pre>
  
  <p>I am getting some unexpected output..even after 2 is added to the nodupes array, the rank for an existing element is -1..</p>
  
  <pre><code>2 rank=-1
  2 is not dupe
  2 rank=-1
  2 is not dupe
  2 rank=-1
  2 is not dupe
  3 rank=-1
  3 is not dupe
  4 rank=-1
  4 is not dupe
  4 rank=4
  5 rank=-1
  5 is not dupe
  6 rank=-1
  6 is not dupe
  Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: 6
      at ...noDupes(BinSearch.java:85)
      at ...main(BinSearch.java:96)
  </code></pre>
  
  <p>I couldn't figure out what I am doing wrong..can someone help?</p>