[Python] Improve this O(N) linear search to O(log N) time complexity

I am trying to solve this Geeks for Geeks problem:

Find the element that appears once


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.

Your Task:
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.

Expected Time Complexity: O(Log(N)).
Expected Auxiliary Space: O(1).

Constraints
0 < N <= 10^6
0 <= A <= 10^9
​

My approach:

For Given Array:A & Size:N
Initialize i With 0 i=0 # i is index reference in array traversal
loop through 0 to N-1# While i<N :
Select i^thelement from Array :A# select=A
Creates A Sub-array(next) does not contain select # next=A[i+1:]
Now compare the next (sub-array) with select
If it contains a duplicate/copy of select
Push select to a new sub-array(previous) # previous keep record of visted element
Update i to +1 & repeat this process
next tym new value get selected ini as select=A[i+1]
Check if it exist in sub-array next&&
If The previous sub array also not contained select#Hopefully it is traversed first tym and it is unique
return the i^th element which doesn't inside both previous and next sub-array
​

Code:

# Function to recognize singular element i

def check(list,n):
i=0
select=0
next=0
previous=[]
while(i<n):
select=list
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()


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.

Continue reading...