### Lab3.1 Finding the Odd Number of Occurrence

You are given a sorted list of numbers where one number appears odd number of times. All other numbers appear even number of times. You are required to design an efficient algorithm to find the number that appears odd number of times. I'm using the Use Divide and Conquer method which runs at $\Theta(\log(n))$

As an example, if the sorted list is
[1, 1, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6] then the odd occurrence number is 2

L1 = [1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 6, 6, 7]

def FindOddNumber(L):

length = len(L);

# If the length of L is 0, return nothing
if (length == 0): return

# If length of L is 1, then that's the odd occurence
if (length == 1): return L[0]

# Find the mid index
mid_index = length / 2
# Initiate index counters to count left and right
l_counter = 0
r_counter = 0

# Count occurences of the mid element to right until
# the end is reached
while ((L[mid_index] == L[mid_index + (r_counter + 1)])):
r_counter = r_counter + 1;
# If the indexes are outbound, break it
if ((mid_index + (r_counter + 1)) > (length - 1)):
break

# Count occurences of the mid element to left until
# the begining is reached
while ((L[mid_index] == L[mid_index - (l_counter + 1)])):
l_counter = l_counter + 1;
# If the indexes are outbound, break it
if ((mid_index - (l_counter + 1)) < 0):
break

# Deduct one to further decisions
counter = r_counter + l_counter

# If counter is odd, then that is not the odd occurence
if (counter % 2) != 0:
# If right count is odd, there are even number of
# elements in the right side. That means that side
# doesn't contain the odd occurence
LL = L[(mid_index + r_counter + 1):]
# If left count is odd, there are even number of
# elements in the left side. That means that side
# doesn't contain the odd occurence
LR = L[:(mid_index - l_counter)]

# List with odd number of elements have the odd
# occurence
if (len(LL) % 2 == 0):
return FindOddNumber(LR)
else:
return FindOddNumber(LL)

# Else that is the odd occurence
else:
return str(L[mid_index])

print FindOddNumber(L1)