What is Binary Search?

Binary search is a search algorithm that divides the search interval by half every time. That also means that the time complexity of binary search is O(log n)

Templates

Binary search can:

• find single element in a sorted array
• find first index satisfying a condition

Find single element in a sorted array

def binary_search(arr, target):
    left, right = 1, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        elif arr[mid] > target:
            right = mid - 1
        else:
            return mid
    return -1

Find first index satisfying a condition

Finding the first index satisfying a condition is the same as finding the first true value of a true-false array.
ex: [False, ... False, True, ... True]

Things to note:

• left and right should include and read & write space
• while loop halts when left == right
• after the while loop:
  • left is the first index satisfying condition() == True
  • left - 1 is the last index satisfying condition() == False

def condition():
    pass

def binary_search(arr):
    left, right = 1, len(arr)-1
    while left < right:
        mid = (left + right) // 2
        if condition():
            right = mid
        else:
            left = mid + 1
    return left