FindUniqueBinarySearch

import java.util.Arrays;
import java.util.HashSet;
import java.util.Random;
import java.util.Set;

public class FindUniqueBinarySearch {
  public static void main(String[] argv) {
    FindUniqueBinarySearch bs = new FindUniqueBinarySearch();
    Set <Integer> set = new HashSet<Integer>();
    Random rnd = new Random();

    for (int N = 1; N < 15; N += 2) {
      int doubleCount = N / 2;
      set.clear();
      int[] A = new int[N];
      int i = 0;
      while (i < doubleCount) {
        int num = rnd.nextInt();
        if (set.contains(num)) {
          continue;
        }
        set.add(num);
        A[2 * i] = A[2 * i + 1] = num;
        i++;
      }

      // add unique one
      while (true) {
        int num = rnd.nextInt();
        if (set.contains(num)) {
          continue;
        } else {
          A[A.length - 1] = num;
          break;
        }
      }

      Arrays.sort(A);

      System.out.println(Arrays.toString(A));
      System.out.println(bs.unique(A) == bs.uniqueXor(A));
    }
  }

  public int uniqueXor(int[] A) {
    int x = 0;
    for (int i: A) {
      x ^= i;
    }
    return x;
  }

  public int unique(int[] A) {
    return unique(A, 0, A.length - 1);
  }

  public int unique(int[] A, int low, int high) {
    if (low == high) {
      return A[low];
    }

    while (low <= high) {
      int mid = low + (high - low)/2;

      if ((mid == 0 && A[mid] != A[mid + 1]) ||
          (mid == A.length - 1 && A[mid] != A[mid - 1]) ||
          (A[mid] != A[mid - 1] && A[mid] != A[mid + 1])) {
        return A[mid];
      } else if (A[mid] == A[mid + 1]) {
        if (mid % 2 == 0) {
          low = mid + 2;
        } else {
          high = mid - 1;
        }
      } else /* A[mid] == A[mid - 1] */ {
        // mid - 1 elements in the left
        if (mid % 2 == 0) {
          high = mid - 2;
        } else {
          low = mid + 1;
        }
      }
    }
    return -1;
  }
}