python - 将此 O(N) 线性搜索改进为 O(log N) 时间复杂度

Question

我正在尝试解决这个Geeks for Geeks 问题：

查找出现一次的元素

给定一个由 N 个正整数组成的排序数组 A[]，其中所有数字恰好出现两次，除了一个仅出现一次的数字。找出只出现一次的数字。

你的任务：
你不需要读取输入或打印任何东西。您的任务是完成函数 search()，它接受两个参数（数组 A 和整数 N）并返回仅出现一次的数字。

预期时间复杂度： O(Log(N))。
预期辅助空间： O(1)。

约束
0 < N <= 10^6
0 <= A[i] <= 10^9

我的做法：

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[i]
Creates A Sub-array(next) does not contain select# next=A[i +1：]
现在比较next（子数组）与select
如果它包含select
推送的副本/副本select到新子数组（previous）＃先前保留访问元素的记录
更新i to +1并重复此过程
下一个tym新值被i选为检查子数组select=A[i+1]
中是否存在&& If子数组 next
previous 也不包含select#Hopefully它是第一个遍历的，它是唯一
的， 返回i^th不在两个数组previous和next子数组中的元素

代码：

# Function to recognize singular element i

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

上面的脚本有效，但不是 O(log N)。我尝试删除额外的变量并将额外的子数组转换为变量以减少时间。

标签： pythonarrayspython-3.xalgorithm