Recursion

Binary Search

Lesson

"Binary Search" is an algorithm you can use to quickly search through Sorted Arrays and other sorted data structures. We'll walk you through how Binary Search works below.

Problem: Given a sorted array arr, and a target number target, return the index of the target. If the target isn't in the array, return None.

The array contains unique elements.

First Few Test Cases:

To solve this problem efficiently, you should use Binary Search. Binary Search is when you look at the middle of the element of your Sorted Array, and use it to eliminate half the elements from your search. For example, say we're looking for the number 3.

First, the binary search looks at middle element in the array:

Next the binary search compares the number we're searching for with the middle element. The number we're searching for (3) is less than the middle element (4). This means the number we're searching for must be to the left of the middle element:

We eliminated half of the array from the search after doing a single comparison. We can continue using the same logic to search the remaining elements [1, 2, 3], and so on. We stop when we've found our number or eliminated everything.

We want to create a function that does a Binary Search from index i to index j in the array.

1. Recursion

To do Binary Search, we always look at the middle element between i and j to decide what to search next.

If the middle element is less than the target, we search the left half of the elements next.

If the middle element is greater than the target, we search the right half of the elements next.

If the middle element equals the target, we're done.

Putting these three conditions together, we get our recursion:

We found the middle index by taking the average of i and j, which is $\texttt{ mid = }\frac{\texttt{i+j}}{2}$ . We also round mid down to the nearest integer using the syntax "//" to make sure that mid is always a valid index, and doesn't contain any decimals.

2. Base case

We need to figure out when our recursion breaks. This happens when the indexes i and j cross each other, because this is not a valid interval to search. In this case, we know the target is not in the array.

3. Code

Combining the recursion and the base case, we get:

Time Complexity $O(\log n)$ . Halving the search every step means Binary Search does $\log_2(n)$ operations.

Space Complexity $O(\log n)$ . search calls itself up to $\log n$ times, so the Call Stack gets $\log n$ calls deep.

You can easily convert this to iterative code:

Time Complexity $O(\log n)$

Space Complexity $O(1)$

Here's an explanation of why $\log n$ shows up:

Let's use an example. Say we're searching this array for the value 3. The array starts out with $n$ total elements.

\notag \texttt{[1,2,3,4,5,6,7]}

In the next step, we're only searching half the elements ( $n/2$ ).

\notag \texttt{[1,2,3]}

After that we're only searching half of those elements ( $n/4$ ).

\notag \texttt{[3]}

The binary search stops when it's gotten down to 1 single element.

We know that every step, the binary search halves the number of elements it searches. This means if it's done $S$ steps, then it's halved the array $S$ times. At that point, it's searching $n/2^S$ elements.

The binary search stops when we're left with a single element. This gives us an equation - the total number of elements at that point $\frac{n}{2^S}$ is equal to 1:

\notag \frac{n}{2^S} = 1

Multiplying both sides by $2^S$ gives:

\notag n = 2^S

Taking the log of both sides gives:

\notag \log_2(n) = S

This equation tells us that a binary search stops when the number of steps we've done, $S$ , is equal to $\log_2 n$ .

Intuitively, this is obvious - we're halving the size of the array at every step of the search. This means that if we double the size of our input, we know we only have to do 1 extra step in the binary search. That's exactly what $O(\log n)$ means. (the definition of $\log_2(n)$ is that when you double n, log(n) increases by 1).

You might be wondering why anyone would store their data in a Sorted Array like in this problem and search for elements using Binary Search, when they could have just used a Set the whole time to do even better. The answer is that this is just a common interview problem. You'd indeed typically use a Set instead.

In the next few examples, we'll see that Binary Search is optimal when you want to search for an element that's less than a certain number (or $\le, \ge, \gt$ ). Generally, binary search is useful when you want to the biggest element less than a number, or vice versa (you can think of this as the sole purpose of binary search).

Mark as Completed:

Submits:

binarySearch

Test your code to get an output here!

binarySearch(

)

Test your code to get an output here!