DEV Community

Alex Kang
Alex Kang

Posted on

Binary Search Templates in Python

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Top comments (0)