binary_search_leftmost

"""
Created on Fri Feb 15 17:26:21 2019

@author: Naomi Toshiba
"""

'''
function binary_search_leftmost(A, n, T):
    L := 0
    R := n
    while L < R:
        m := floor((L + R) / 2)
        if A[m] < T:
            L := m + 1
        else:
            R := m
    return L
'''

numberli1=[1, 2, 3, 4, 4, 4, 4, 4, 5, 6, 7, 8, 9]
number2=4
def binary_search_leftmost(sorted_list,value):


    move_count=1
    left =0
    right = len(sorted_list)
    while left < right :
        mid = int((left + right)/2)


        if sorted_list[mid]<value:
            left = mid+1
            move_count +=1
        else:
            right = mid
            move_count +=1


    return left,move_count

pos1,m1=binary_search_leftmost(numberli1,number2)

print('The number is the ', str(pos1+1),' number in the list.')
print('binary search leftmost took ' ,str(m1),'times to move')