search_unique.py

# Problem: Given a sorted array in which all elements
# appear twice (one after one) and one element
# appears only once. Find that element
# Constraints: in O(log n) complexity.
defsearchUnique(arr, low, high):
# Base Cases
# 1. low is greater than high
# 2. Array with single element
iflow>high:
returnNone
iflow==high:
returnarr[low]
# Find the middle element
mid=low+ (high-low) //2
# if the middle element lies at even place,
# check i and i+1, if they are same, go to right else left
ifmid%2==0:
ifarr[mid] ==arr[mid+1]:
returnsearchUnique(arr, mid+2, high)
else:
returnsearchUnique(arr, low, mid)
# if the middle element lies at odd place,
# check i-1 and i, if they are same, go to right else left
# Replace mid by mid-1 for above block
else:
ifarr[mid-1] ==arr[mid]:
returnsearchUnique(arr, mid+1, high)
else:
returnsearchUnique(arr, low, mid-1)


array= [1, 1, 2, 4, 4, 5, 5, 6, 6]
result=searchUnique(array, 0, len(array) -1)
print(result)
# Result: 2