#algo #python

non_repeating_el_sorted_array.py

# You are given a sorted array of integers.
# Every element appears twice consequently, except for one.
# Find the non-repeating element in O(log n).

def f(list, start, end):
	mid = (start+end) / 2

	# Two elements left
	if end-start <= 1:
		prev = list[start-1]
		first = list[start]
		second = list[end]

		if first == second:
			return None
		else:
			return first if first != prev else second

	cur = list[mid]
	prev = list[mid-1]

	even = mid % 2 == 0

	if even:
		if prev != cur:
			ret = f(list, mid+1, end)
		else:
			ret = f(list, start, mid-1)
		
	else:
		if prev != cur:
			ret = f(list, start, mid-1)			
		else:
			ret = f(list, mid+1, end)

	return ret if ret else list[mid]

case1 = [1,1,3,3,4,5,5,7,7,8,8]
print(f(case1, 0, len(case1)-1) == 4)

case2 = [1,1,3,3,4,4,5,5,7,7,8]
print(f(case2, 0, len(case2)-1) == 8)

case3 = [1,3,3,4,4,5,5,7,7,8,8]
print(f(case3, 0, len(case3)-1) == 1)

case4 = [1,1,3,4,4,5,5,7,7,8,8]
print(f(case4, 0, len(case4)-1) == 3)

case5 = [1,1,3,3,4,4,5,7,7,8,8]
print(f(case5, 0, len(case5)-1) == 5)