Binary Search

Aka: half-interval search, logarithmic search, binary chop

Efficient method to find an element assuming the list is sorted. This allows us to disregard half the list on each attempt, thus leading to a boost from linear to logarithmic time.

Pros	Cons
Most efficient general-purpose method to find an element	Requires the collection to be sorted

Implementations

Python : Custom implementation

Python: Custom implementation

def binary_search(target, sorted_list):
    low, high = 0, len(sorted_list) - 1
    while low <= high:
        middle = low + int((high-low)/2)
        if sorted_list[middle] == target:
            return middle
        elif sorted_list[middle] < target:
            low = middle + 1
        else:
            high = middle - 1
    return -1

Python : Custom Implementation 2

Python: Custom Implementation 2

def binary_search(target, sorted_list):
    low, high = 0, len(sorted_list)
    while low < high:
        middle = low + int((high-low)/2)
        if sorted_list[middle] == target:
            return middle
        elif sorted_list[middle] < target:
            low = middle + 1
        else:
            high = middle
        return -1

Python : Custom using related built-in function

Python: Custom using related built-in function

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError

LeetCode Problems

Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

easy

Performance
Worst-case	O(log n)
Average	O(log n)
Best-case	O(1)
Worst-case space	O(1)