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 targest. 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  mid = i+j2\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(logn)O(\log n). Halving the search every step means Binary Search does log2(n)\log_2(n) operations.

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

You can easily convert this to iterative code:

Time Complexity O(logn)O(\log n)

Space Complexity O(1)O(1)

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

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).

Mark as Completed:
Submits:
binarySearch
Test your code to get an output here!
binarySearch(
)
Test your code to get an output here!