Posted onApr 28, 2023 • Originally published atjarednielsen.com

How to Code the Binary Search Algorithm

#algorithms #career #javascript #python

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 JavaScriptand Python.

This article originally published atjarednielsen.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 arrayWHEN I request a specific valueTHEN 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 containingone number, for example:[1].

Let's pseudocode this:

INPUT arr, numIF arr[0] == num    RETURN 'Bingo!'ELSE     RETURN FALSE

This is less of asearch and more of a guessing game. What's the next smallest problem? An array containingtwo 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? Wecould write conditionals for every index, but will it scale?

Can we cut this array in half? Not cleanly.

But wecan select the index in the middle and check if it's greater or less thannum. Ifnum is less than the middle index, we willpivot and compare the preceding value. And ifnum is greater than the middle index, we willpivot and check the succeeding value. Hey! Let's call this indexpivot.

If our array is[1, 2, 4], the ourpivot is2. 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:

In order to scale, we can no longer "hard code" the value stored inpivot.
There's no "middle index". So what value do we choose forpivot?

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.

Ifpivot is equal to 2, the value at that index in our array is4.

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, ourpivot is equal to 2.

The value stored in the 2 index is3.

Previously, we hard coded the conditional checks on either side of the pivot. Will that work here?

No, because there are nowtwo 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 awhile. Ourwhile loops need a conditional. What do we want to use here?

Ifpivot is less thannum, then on the next iteration we need to start with a value greater thanpivot. But we need to ensure we are still checkingall of the values greater thanpivot.

And ifpivot is greater thannum, then on the next iteration we need to start with a value less thanpivot. And, as above, we need to ensure we are still checkingall of the values less thanpivot.

Do you see a pattern?

Before we implement ourwhile 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 for5.

On our first iteration, we setpivot to3.

We start our conditional checks and see thatpivot is not equal tonum, but that itis less thannum. We can now ignore the values up to and includingpivot.

In the next iteration, we'll start searching atpivot + 1, which is4.

What happens in the next iteration?

We setpivot 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 newpivot.

We need to set apivot from the remaining values to be checked. In our case, that's:

[4, 5]

If we floor the length ofthis array divided by 2, we get 1. But we know that's notactually 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...

constpowers=[1,2,4,8,16,32,64,128,256,512];constbinarySearch=(arr,num)=>{letstartIndex=0;letendIndex=(arr.length)-1;while(startIndex<=endIndex){letpivot=Math.floor((startIndex+endIndex)/2);if(arr[pivot]===num){return`Found${num} at${pivot}`;}elseif(arr[pivot]<num){startIndex=pivot+1;}else{endIndex=pivot-1;}}returnfalse;}

How to Code the Binary Search Algorithm in Python

Now let's see it in Python...

importmathpowers=[1,2,4,8,16,32,64,128,256,512]defbinarySearch(arr,num):startIndex=0endIndex=len(arr)-1while(startIndex<=endIndex):pivot=math.floor((startIndex+endIndex)/2)if(arr[pivot]==num):returnf"Found{num} at index{pivot}"elif(arr[pivot]<num):startIndex=pivot+1else:endIndex=pivot-1returnfalse

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.