binary search find an element in a sorted array in ascending order for binary search tn tn2 o1 the recurrence relation apply masters theorem for computing run time complexity of recurrence relations tn atnb fn here a 1 b 2 log a base b 1 also here fn nc logkn k 0 c log a base b so tn onc logk1n ologn worstcase complexity ologn reference https en wikipedia orgwikibinarysearchalgorithm in this below function we are passing array it s first index last index and value to be searched worstcase complexity ologn reference https en wikipedia orgwikibinarysearchalgorithm here in logic section first we are checking if low is greater than high which means its an error condition because low index should not move ahead of high index for binary search t n t n 2 o 1 the recurrence relation apply masters theorem for computing run time complexity of recurrence relations t n at n b f n here a 1 b 2 log a base b 1 also here f n n c log k n k 0 c log a base b so t n o n c log k 1 n o log n worst case complexity o log n reference https en wikipedia org wiki binary_search_algorithm in this below function we are passing array it s first index last index and value to be searched worst case complexity o log n reference https en wikipedia org wiki binary_search_algorithm here in logic section first we are checking if low is greater than high which means its an error condition because low index should not move ahead of high index this mid will not break integer range go search in the left subarray go search in the right subarray
def binary_search(array, query):
    

    low, high = 0, len(array) - 1
    while low <= high:
        mid = (high + low) // 2
        val = array[mid]
        if val == query:
            return mid

        if val < query:
            low = mid + 1
        else:
            high = mid - 1
    return None


def binary_search_recur(array, low, high, val):
    

    if low > high:       
        return -1
    mid = low + (high-low)//2   
    if val < array[mid]:  
        return binary_search_recur(array, low, mid - 1, val) 
    if val > array[mid]:
        return binary_search_recur(array, mid + 1, high, val) 
    return mid