Summary - Binary search

Implement binary search and print the result.

Summary - Binary search

In this group you learned binary search's logic, left-right pointers, base case and recursive version. Complexity is O(log n).

Binary search is the fastest search method on sorted arrays. The search space halves at each step.

Exercise Binary search (simple)

Write binary_simple(arr, target). Search with while. Print 2 with print(binary_simple([10, 20, 30, 40, 50], 30)).

Show example solution

def binary_simple(arr, target):
    # Simple binary search
    lo = 0
    hi = len(arr) - 1
    while lo <= hi:
        m = (lo + hi) // 2
        if arr[m] == target:
            return m
        if arr[m] < target:
            lo = m + 1
        else:
            hi = m - 1
    return -1
print(binary_simple([10, 20, 30, 40, 50], 30))

Test yourself

Summary - Binary search: match the terms

Binary search

Sorted array
O(log n)

Speed
mid

Middle
left <= right

Loop

Binary search

Binary search ____ the search space each step.

Show answer

Binary search halves the search space each step.

Why is binary search fast?
- Visits every element
- Sorts the array
- Halves the search space
- Uses hash
Show answer

Halves the search space — It halves the search space.

Next lesson: What is a linked list?

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies