Binary Search

Given an an array of sorted numbers, write a function to search a given number in the array.

For example, if you're given the following sorted array:

arr = [1, 3, 5, 6, 7, 8, 9]

A search for 7 should return True, while a search for 2 should return False.

How Binary Search works

Binary search of a number works on a sorted array by removing half of the array on each step.

First we start with the middle number. If the target number is greater than the middle number, then we know the target number is in the left half of the array.

Otherwise, our target number is in the right half.

We repeat these steps until we either find our target number or have eliminated the entire array.

Step through these steps visually below:

Since the problem is cut in half in each step, the time complexity of binary search is O(log(n))

Try it

Before you look at the solution, try to implement it yourself.

def binary_search(A: list[int], target: int) -> bool:
    # implement binary_search
    return False

1def binary_search(A: list[int], target: int) -> bool:
2    # implement binary_search
3    return False
4

Solution

5 Essential Sorting & Searching Coding Interview Problems

Master Sorting & Searching by trying the coding challenges below.

Want to confidently pass your next coding interview?

Stack Bash helps new and veteran software engineers master data structures and algorithms for technical interviews.