title: Improve this O(N) linear search to O(log N) time complexity
body: <p>I am trying to solve this <a href="https://practice.geeksforgeeks.org/problems/element-appearing-once2552/1" rel="nofollow noreferrer">Geeks for Geeks problem</a>:</p>
  <blockquote>
  <h3 id="find-the-element-that-appears-once-38he">Find the element that appears once</h3>
  <p>Given a sorted array A[] of N positive integers having all the numbers occurring exactly twice, except for one number which will occur only once. Find the number occurring only once.</p>
  <p><strong>Your Task:</strong><br />
  You don't need to read input or print anything. Your task is to complete the function search() which takes two arguments(array A and integer N) and returns the number occurring only once.</p>
  <p><strong>Expected Time Complexity:</strong> O(Log(N)).<br />
  <strong>Expected Auxiliary Space:</strong> O(1).</p>
  <p><strong>Constraints</strong><br />
  0 &lt; N &lt;= 10^6<br />
  0 &lt;= A[i] &lt;= 10^9</p>
  </blockquote>
  <p>My approach:</p>
  <blockquote>
  <p>For Given <code>Array:A</code> &amp; <code>Size:N</code><br/>
  Initialize i With 0 <code>i=0</code> # i is index reference in array traversal<br>
  loop through <code>0 to N-1</code># While i&lt;N :<br>
  Select <code>i^th</code>element from <code>Array :A</code># select=A[i]<br>
  Creates A  Sub-array(next) does not contain <code>select</code> # next=A[i+1:] <br>
  Now compare the <code>next</code> (sub-array) with <code>select</code> <br>
  If it contains a duplicate/copy of <code>select</code> <br>
  Push <code>select</code> to a <strong>new sub-array</strong>(<code>previous</code>) # previous keep record of visted element<br>
  Update <code>i to +1</code> &amp; repeat this process<br>
  next tym <strong>new value</strong> get selected in<code>i</code> as <code>select=A[i+1]</code> <br>
  Check if it exist in <strong>sub-array</strong> <code>next</code>&amp;&amp; <br>
  If The <code>previous</code> <strong>sub array</strong> also  not contained <code>select</code>#Hopefully it is traversed first tym  and it is <strong>unique</strong><br>
  return the <code>i^th</code> element which doesn't inside both <code>previous</code> and <code>next</code> sub-array</p>
  </blockquote>
  <p>Code:</p>
  <pre><code># Function to recognize singular element i
  
  def check(list,n):
   i=0
   select=0
   next=0
   previous=[]
   while(i&lt;n):
    select=list[i]
    next=list[i+1:]
    if select in next:
      previous.append(select)
    elif select in previous:
      pass
    else:
     return select
    i+=1
    
  
  
  
  # Driver Code
  def main():
   list=[]
   n =int(input('Enter Size of array:'))
   for a in range(0,n):
    x=int(input('Array[{}]='.format(a)))
    list.append(x)
   i=check(list,n)
   print('The No.is :',i)
  
  main()
  </code></pre>
  <p>The above script works but is not O(log N). I tried removing extra variable and converted extra sub-array to variable to reduce time.</p>