DSA — Searching Algorithms

Binary Search

Halve the search space each step by comparing target with the middle element. Requires a sorted array. Efficiency: O(log n).

— min read
O(log n)Time
O(1)Space
SortedRequired
Divide& Conquer
✓Interview Fav
01Step-by-Step Search
Array must be sorted. Press Find.
Logic
Python
Practice
01
Initial Range
Set `lo = 0` and `hi = n - 1`.
02
Middle Check
Calculate `mid = (lo + hi) // 2`. If `arr[mid] == target`, done!
03
Divide
If target is larger, search right half (`lo = mid + 1`). Otherwise, search left half (`hi = mid - 1`).
def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if arr[mid] == target: return mid
        elif arr[mid] < target: lo = mid + 1
        else: hi = mid - 1
    return -1
Search Mastery0 / 3 solved
#01Search in Rotated SortedGoogle
#02First and Last PositionMeta
#03Search Insert PositionZomato
← Linear Search