title: Find element of an array that appears only once in O(logn) time
body: <p>Given an array <code>A</code> with all elements appearing twice except one element which appears only once. How do we find the element which appears only once in <code>O(logn)</code> time? Let's discuss two cases.</p>
  <ol>
  <li>Array is always sorted and elements are in sequential order. Let's assume <code>A = [1, 1, 2, 2, 3, 4, 4, 5, 5, 6, 6]</code>, we want to find <code>3</code> in <code>log n</code> time because it appears only once.</li>
  <li>When the array is not sorted and the elements are not in sequential order.</li>
  </ol>
  <p>I can only come up with a solution of using the XOR operator on the binary representation of the integers as explained <a href="https://www.youtube.com/watch?v=eXWjCgbL01U" rel="nofollow noreferrer">Here</a>, and at the end, the binary string will represent the element which appears only once because duplicates will cancel out. But it takes <code>O(n)</code> time. How can we do better than that?</p>