Jared NielsenIf you want to learn how to code, you need to learn algorithms. Learning algorithms improves your problem solving skills by revealing design patterns in programming. In this tutorial, you will learn how to code the binary search algorithm in JavaScript and Python.
This article originally published at jarednielsen.com
How to Code the Binary Search Algorithm in JavaScript and Python
Programming is problem solving. There are four steps we need to take to solve any programming problem:
Understand the problem
Make a plan
Execute the plan
Evaluate the plan
Understand the Problem
To understand our problem, we first need to define it. Let’s reframe the problem as acceptance criteria:
GIVEN a sorted array
WHEN I request a specific value
THEN I am returned the location of that value in the array
That’s our general outline. We know our input conditions, a sorted array, and our output requirements, the location of a specific value in the array, and our goal is to improve the performance of a linear search.
Let’s make a plan!
Make a Plan
Let’s revisit our computational thinking heuristics as they will aid and guide is in making a plan. They are:
Decomposition
Pattern recognition
Abstraction
Algorithm design
The first step is decomposition, or breaking our problem down into smaller problems. What's the smallest problem we can solve?
An array containing one number, for example: [1].
Let's pseudocode this:
INPUT arr, num
IF arr[0] == num
RETURN 'Bingo!'
ELSE
RETURN FALSE
This is less of a search and more of a guessing game. What's the next smallest problem? An array containing two numbers: [1, 2].
INPUT arr, num
IF arr[0] == num
RETURN 'Found num in the 0 index`
ELSE IF arr[1] == num
RETURN 'Found num in the 1 index`
ELSE
RETURN FALSE
This is still a guessing game, but now it's binary! What did we do when we wrote those two conditionals? We cut the problem in half: [1] and [2].
Let's add one more: [1, 2, 4]. Now what? We could write conditionals for every index, but will it scale?
Can we cut this array in half? Not cleanly.
But we can select the index in the middle and check if it's greater or less than num. If num is less than the middle index, we will pivot and compare the preceding value. And if num is greater than the middle index, we will pivot and check the succeeding value. Hey! Let's call this index pivot.
If our array is [1, 2, 4], the our pivot is 2. Let's pseudocode this:
INPUT arr, num
SET pivot TO arr[1]
IF arr[pivot] == num
RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
RETURN 'Found num in the 0 index'
ELSE
RETURN 'It's gotta be in the 2 index...'
Let's work with a slightly larger array: [1, 2, 4, 8].
There are a few small problems we need to solve here:
In order to scale, we can no longer "hard code" the value stored in
pivot.There's no "middle index". So what value do we choose for
pivot?
Let's address the first problem first: we can simply divide the array in two.
INPUT arr, num
SET pivot TO LENGTH OF arr DIVIDED BY 2
IF arr[pivot] == num
RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
RETURN 'Found num in the 0 index'
ELSE
RETURN 'It's gotta be in the 2 index...'
Using the example above, our array contains four elements. If we divide the length of our array by two, pivot will be equal to 2.
If pivot is equal to 2, the value at that index in our array is 4.
But what if there's an odd number of elements in the array?
[1, 2, 3, 4, 5]
If we divide the length of the array by 2, we get 2.5.
We simply need to round up or down. Let's round down. Our pseudocode now reads:
INPUT arr, num
SET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2
IF arr[pivot] == num
RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
RETURN 'Found num in the 0 index'
ELSE
RETURN 'It's gotta be in the 2 index...'
When we divide the length of this array by 2 and floor the returned value, our pivot is equal to 2.
The value stored in the 2 index is 3.
Previously, we hard coded the conditional checks on either side of the pivot. Will that work here?
No, because there are now two values we need to check on either side of our pivot.
It's time to iterate!
Because we don't know how long our loop needs to run, let's use a while. Our while loops need a conditional. What do we want to use here?
If pivot is less than num, then on the next iteration we need to start with a value greater than pivot. But we need to ensure we are still checking all of the values greater than pivot.
And if pivot is greater than num, then on the next iteration we need to start with a value less than pivot. And, as above, we need to ensure we are still checking all of the values less than pivot.
Do you see a pattern?
Before we implement our while iteration, let's translate these conditionals to pseudocode:
INPUT arr, num
SET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2
IF arr[pivot] == num
RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
START SEARCHING IN THE NEXT ITERATION AT pivot + 1
ELSE
SEARCH UP TO pivot - 1 IN THE NEXT ITERATION
Let's step through a hypothetical scenario using our five element array and searching for 5.
On our first iteration, we set pivot to 3.
We start our conditional checks and see that pivot is not equal to num, but that it is less than num. We can now ignore the values up to and including pivot.
In the next iteration, we'll start searching at pivot + 1, which is 4.
What happens in the next iteration?
We set pivot to the floor of the length of our array divided by 2, which is 2.
Hey! Wait! We already checked this value.
We need a new pivot.
We need to set a pivot from the remaining values to be checked. In our case, that's:
[4, 5]
If we floor the length of this array divided by 2, we get 1. But we know that's not actually the 1 index.
What do we do here?
We get abstract!
Let's declare variables to store these values in each iteration:
SET start index TO 0
SET end index TO THE LENGTH OF THE ARRAY - 1
Finally, we need to refactor our conditional statements to reassign these values in each iteration:
INPUT arr, num
SET start index TO 0
SET end index TO THE LENGTH OF THE ARRAY - 1
WHILE
SET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2
IF arr[pivot] == num
RETURN 'Found num at pivot'
ELSE IF arr[pivot] < num
SET start index TO pivot + 1
ELSE
SET end index TO pivot - 1
RETURN FALSE
Execute the Plan
Now it's simply a matter of translating our pseudocode into the syntax of our programming language.
How to Code the Binary Search Algorithm in JavaScript
Let's start with JavaScript...
const powers = [1, 2, 4, 8 ,16, 32, 64, 128, 256, 512];
const binarySearch = (arr, num) => {
let startIndex = 0;
let endIndex = (arr.length)-1;
while (startIndex <= endIndex){
let pivot = Math.floor((startIndex + endIndex)/2);
if (arr[pivot] === num){
return `Found ${num} at ${pivot}`;
} else if (arr[pivot] < num){
startIndex = pivot + 1;
} else {
endIndex = pivot - 1;
}
}
return false;
}
How to Code the Binary Search Algorithm in Python
Now let's see it in Python...
import math
powers = [1, 2, 4, 8 ,16, 32, 64, 128, 256, 512]
def binarySearch(arr, num):
startIndex = 0
endIndex = len(arr)-1
while (startIndex <= endIndex):
pivot = math.floor((startIndex + endIndex)/2)
if (arr[pivot] == num):
return f"Found {num} at index {pivot}"
elif (arr[pivot] < num):
startIndex = pivot + 1
else:
endIndex = pivot - 1
return false
Evaluate the Plan
Can we do better?
Of course! This is just the beginning of our exploration of search algorithms. There are variations on binary search as well as data structures based on binary search that improve the performance.
A is for Algorithms
Give yourself an A. Grab your copy of A is for Algorithms
