How to Code the Binary Search Algorithm

If 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:

1. Understand the problem

2. Make a plan

3. Execute the plan

4. Evaluate the plan

Understand the Problem

To understand our problem, we first need to define it. Lets reframe the problem as acceptance criteria:

GIVEN a sorted arrayWHEN I request a specific valueTHEN I am returned the location of that value in the array

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

Lets make a plan!

Make a Plan

Lets 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, numIF 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, numIF 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, numSET 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:

1. In order to scale, we can no longer "hard code" the value stored in pivot.

2. 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, numSET pivot TO LENGTH OF arr DIVIDED BY 2IF 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, numSET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2IF 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, numSET pivot TO THE FLOOR OF THE LENGTH OF arr DIVIDED BY 2IF arr[pivot] == num    RETURN 'Found num at pivot'ELSE IF arr[pivot] < num    START SEARCHING IN THE NEXT ITERATION AT pivot + 1ELSE     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 0SET 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, numSET start index TO 0SET end index TO THE LENGTH OF THE ARRAY - 1WHILE    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 mathpowers = [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