Binary search idea

Halve the range each step on a sorted array for O(log n).

Binary search logic

Binary search finds a target in a sorted array in O(log n) time. It halves the search space at each step.

It first checks the middle element. If the target equals it, it is found. If smaller, it searches the left half; if larger, the right half.

Sorted requirement

Binary search only works on sorted arrays. In an unsorted array, the middle element cannot tell which half to search.

Therefore you must sort the array before using binary search. Since sorting is O(n log n), for a single search linear search may be better.

Exercise Binary search

Write binary_search(arr, target). Search with left-right pointers. Print 3 with print(binary_search([1, 3, 5, 7, 9], 7)).

Show example solution

def binary_search(arr, target):
    # Binary search
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1
print(binary_search([1, 3, 5, 7, 9], 7))

Test yourself

On which array does binary search work?
- Only empty
- Only sorted
- Only unsorted
- Any array
Show answer

Only sorted — It works only on sorted arrays.

Complexity

Binary search runs in ____ time.

Show answer

Binary search runs in O(log n) time.

Binary search idea: match the terms

Binary search

Sorted array
O(log n)

Speed
Middle element

Divide
Sorted

Requirement

Next lesson: Left right pointers

We Are Enhancing Your Experience

Cookie Preferences

Strictly Necessary Cookies

Analytical Cookies