# luis ulloa
def bestAcornBranch(branches):
# at most log(n) + 1 iterations
n = len(branches)
left = 0
right = n-1
while left <= right:
mid = (left + right) // 2 # integer division (python3)
if branches[mid] == True: # current branch breaks (True)
# check base case
if mid - 1 <= 0 or branches[mid-1] == False: # we are on the lowest breaking branch
return mid
# else, ignore right half, since they all break
right = mid - 1
else: # current branch doesn't break (False)
# other base case
if mid+1 < n and branches[mid+1] == True: # we're below the branch, if topmost is false, no branches work
return mid + 1
# else, ignore left half, since none of them break
left = mid + 1
return -1 # acorn never breaks
x = [False, False, False, True, True, True]
print(bestAcornBranch(x), 3)
x = [False, False, False, False, True, True]
print(bestAcornBranch(x), 4)
x = [False, False, False, False, False, True]
print(bestAcornBranch(x), 5)
x = [False, False, False, False, False, False]
print(bestAcornBranch(x), -1)
x = [True, True, True, True, True, True]
print(bestAcornBranch(x), 0)
x = [False, True, True, True, True, True]
print(bestAcornBranch(x), 1)
x = [False, False, True, True, True, True]
print(bestAcornBranch(x), 2)
x = [False, True, True, True, True, True, True]
print(bestAcornBranch(x), 1)
x = [False, False, False, False, False, False, True]
print(bestAcornBranch(x), 6)
