Binary search summary

Assumption

The list arr is non-descending.

Normal binary search

def binary_search(arr, target):
    "Return the index where target is found, otherwise return -1."
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = low + (high - low) // 2
        if arr[mid] < target:
            low = mid + 1
        elif arr[mid] > target:
            high = mid - 1
        else:
            return mid
    return -1

Find the leftmsot element

def binary_search_leftmost(arr, target):
    "Return the leftmost index where to insert target in arr."
    low, high = 0, len(arr)
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] < target:
            low = mid + 1
        else:
            high = mid
    return low

Find the rightmsot element

def binary_search_rightmost(arr, target):
    "Return the rightmost index where to insert target in arr."
    low, high = 0, len(arr)
    while low < high:
        mid = low + (high - low) // 2
        if arr[mid] <= target:
            low = mid + 1
        else:
            high = mid
    return low

N.B. : It's the condition arr[mid] <= target that makes the difference between leftmost and rightmost.