DEV Community: Vitor Leal

Understanding the binary search algorithm

Vitor Leal — Fri, 09 Apr 2021 11:48:45 +0000

The binary search

Imagine you're given this big phonebook full of people's names and their respective phone numbers. Your task is to find John's phone number. What would be the easiest and fastest way to find him?

We could start from the first page and flip through each page, one by one, until we finally find John. As you might have thought, this is extremely slow and inefficient. Look at, for example, the phonebook in the image; there are thousands of pages with, possibly, hundreds of names within them. Imagine how long would it take to find John?

We can do better.

We know that this particular phonebook is alphabetically sorted. We know, therefore, that the first page shows names that start with 'A' and the last page shows names that starts with 'Z'. We don't know, however, which page starts showing names with 'J' (John's first character).

Cutting the problem in half

Odds are that if you have this phonebook on your hands, you wouldn't check each page one by one starting from the beginning. You would probably open the phonebook roughly to the middle and check which letter comes up.

Say you do open the phonebook to the middle and you end up on the 'M' session. Now, if you are looking for John, you would ignore everything that's to the right portion of the book since 'J' is smaller than 'M'.

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z

You see how much more efficient that is? In just one step, we cut the problem in half.

Is 'M' the letter we were looking for? No, so let's keep repeating this process until we find the session 'J':

In our first step, we chose letter 'M' as our mid-point. 'M' is not the letter we are looking for, so we can disregard it as well:
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Let's choose our new mid-point: 'F'. 'A' becomes our left-most letter and 'L' our right-most letter.
A B C D E **F** G H I J K L M N O P Q R S T U V W X Y Z
'J' is greater than 'F'; therefore, we can disregard 'F' and everything that's less than it.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Our new mid-point now becomes 'I'. Our left-most letter is now 'G' and the right-most letter is still 'L'.
A B C D E F G H **I** J K L M N O P Q R S T U V W X Y Z
'J' is greater than 'I'; therefore, we can disregard 'I' and everything that's less than it.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Our new mid-point now becomes 'K'. Our left-most letter is now 'J' and our right-most letter is now 'L'.
A B C D E F G H I J **K** L M N O P Q R S T U V W X Y Z
'J' is less than 'K'. We can cut 'K' and 'L', leaving 'J' by itself. Our left-most letter and right-most letter are now the same, and they both point to the letter we want: J.
A B C D E F G H I **J** K L M N O P Q R S T U V W X Y Z

If we were to do this linearly, it would take thousands of steps. With binary search, however, we were able to find our 'J' session in just a few steps.

Converting this idea to code

Repeating the aforementioned process in your mind is easy, but a computer is logical at its core. How do we tell to a computer where is the mid, left-most and right-most point? Let's use Javascript to code this up.

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]

We begin by creating a sorted array with a few numbers in it. Just like the GIF above, we wish to find the number 37.

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

In the beginning, our left-most point points at the beginning of the array; the index 0.

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

let leftMost = 0

And our right-most point points to the last element of the array; the array's length.

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

let leftMost = 0
let rightMost = array.length - 1

Great. We already know our left-most and right-most points. Now we need to find our mid-point.

Before we do so, let's take a step back. Look at the alphabet example I gave above. We repeated the process of cutting the array in half a couple of times. We only stopped when the left-most and right-most points pointed to the same letter and the letter was the one we were looking for: J.. Maybe we need some sort of iteration?

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

let leftMost = 0
let rightMost = array.length - 1

while (leftMost <= rightMost) {
  // TODO
}

Just like the alphabet example, in each step, we do the following:

Calculate the mid-point

let midPoint = (leftMost - rightMost) / 2

If we are lucky and our mid-point is the number we want (37), then just return it.

if (array[midPoint] === numberWeWant) {
  return array[midPoint]
}

Or, if the number we want (37) is greater than the middle, we update the left-most pointer:

if (arr[midPoint] < numberWeWant) {
  let leftMost = midPoint + 1
}

Else, the number we want (37) is less than the middle, we update the right-most pointer:

if (arr[midPoint] < numberWeWant) {
  let leftMost = midPoint + 1
} else {
  let rightMost = midPoint - 1
}

Piecing it all together, we have:

const array = [1, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59]
const numberWeWant = 37

let leftMost = 0
let rightMost = array.length - 1

while (leftMost <= rightMost) {
  let midPoint = (leftMost - rightMost) / 2

  if (array[midPoint] === numberWeWant) {
    return array[midPoint]
  } else if (array[midPoint] < numberWeWant) {
    let leftMost = midPoint + 1
  } else {
    let rightMost = midPoint - 1
  }
}

I made a game in C run in a web browser and so can you

Vitor Leal — Sun, 03 May 2020 13:30:22 +0000

It is undoubtedly true that most of the web is powered by Javascript nowadays; however, recent technologies such as WebAssembly are to change this scene — or, perhaps, some of it, as for reasons that will be noted later. In this article I will be demonstrating how I ported the well-known Snake game built with only C and SDL to web browsers utilizing the aforementioned technology.

What is WebAssembly?

You have most likely heard of the Assembly language — a low-level language with a strong link to the machine code instructions — as this sort of old and cryptic programming language; in simple terms, WebAssembly is the same thing (though not exactly Assembly), but capable of running in most modern web browsers. One of the reasons it shines is the fact it is decoded and compiled to machine code, thus providing a way to run code on the web at near-native speed. Not only that, even though you could learn how to code WebAssembly by hand — which wouldn’t be efficient — , WebAssembly is rather used as a compilation target for low-level languages such as C, C++ and Rust; in Layman’s term, that means you can code in one of these languages, compile it to WebAssembly, and run it in the browser.

Although it is tempting to ditch Javascript — either because you hate it like I do or you want to see new technologies powering the web — and start using WebAssembly for all your web applications, it is important to note that WebAssembly is not a substitute for Javascript. Rather, you can think of JS and WASM as a couple, each taking care of specific parts of your web application. And no, WASM won’t replace Javascript in the near-future, and if it ever does, you will probably be retired by then. Therefore, when should we use WebAssembly? Per its official documentation:

CPU intensive tasks such as games with heavy assets, math calculations, image/video editing, etc.
Porting old other languages’ libraries and applications, thus providing portability and promoting cross-platform.
Live video augmentation, VR and augmented reality (due to its low-latency).
Or, in this case, porting a simple Snake game from C and SDL for the sake of it.

It is believed that the “script” in Javascript — which makes JS seem like a scripting language at first glance — will begin to be a reality with WASM doing the heavy-lifting and JS serving as a complement.

Porting our Snake game built with C and SDL to WebAssembly

Enough with introductions — let’s actually learn how to compile our Snake game to WebAssembly and deploy it on the web. Recall I said compile, therefore we will need another tool that helps us convert our C code to WASM; that is Emscripten, a toolchain that helps us compile C and C++ code into WebAssembly — in Layman’s term, if you ever coded in C or C++, you can think of it as a Clang or GCC that, instead of compiling to machine code, it compiles to WebAssembly. But… what about the SDL library? Lucky for us, since SDL is quite renowned in the game development industry, Emscripten supports it right off the bat.

Setting up Emscripten

First, let’s install the prerequisites.

Windows

You will need Python 2.7 or newer. You can easily download it through this page.

Mac

You will need XCode and its command line tools. Also, you will need to have Git and CMake installed.

Linux

# Install Python
sudo apt-get install python2.7

# Install CMake (optional, only needed for tests and building Binaryen)
sudo apt-get install cmake

# Install Java (optional, only needed for Closure Compiler minification)
sudo apt-get install default-jre

Great, now let’s install Emscripten itself. There’s two ways of downloading it: you can go to its Github page and press the green button titled “Download”, or cloning the repository using the command-line interface.

# Get the emsdk repo
git clone https://github.com/emscripten-core/emsdk.git

# Enter that directory
cd emsdk

Either way, once you are inside the directory, run the following commands:

# Fetch the latest version of the emsdk (not needed the first time you clone)
git pull

# Download and install the latest SDK tools.
./emsdk install latest

# Make the "latest" SDK "active" for the current user. (writes ~/.emscripten file)
./emsdk activate latest

# Activate PATH and other environment variables in the current terminal
source ./emsdk_env.sh

NOTE: if you are using Windows, make sure to run emsdk instead of ./emsdk, and emsdk_env.bat instead of source ./emsdk_env.sh.

Awesome, you are half-way there!

Compiling our Snake game built with C and SDL to WebAssembly

Now that you have Emscripten set up in your OS, it’s time to make certain modifications in order to successfully run our game in the browser. First, code yourself something or, if you wish, head to the source code of the game I have built as an demo for this article.

Head over to main.c, and I will walk you through the necessary changes made in order to make the game compile with Emscripten. As a comparison, here’s the original main.c. As you can see, not that big of a difference: I added two functions that are of Emscripten and #ifdefs for conditional compilation. The rest of the source code is unchanged.

#ifdef __EMSCRIPTEN__
    #include <emscripten.h>
#endif

In order to access Emscripten’s functions, we need to import them. In Layman’s term, the #ifdef serves to detect whether this code is being compiled to WebAssembly or machine code. If the former is true, then we need to include emscripten.h, otherwise it is not necessary.

Now let’s check out this piece of code:

int main(int argc, char* args[])
{
    if(!init())
        return -1;
     else{
         #ifdef __EMSCRIPTEN__
             emscripten_set_main_loop(main_loop, 0, 1);
         #endif
         #ifndef __EMSCRIPTEN__
             while(running)
                 main_loop();
         #endif
     }

    quit_game();
    return 0;
}

If there was a error in the initialization of the game, return -1 and quit the game. Else, again we check if this game is being compiled with Emscripten; if it is, we need to use the emscripten_set_main_loop() function rather than just calling the function ourselves. Why? Infinite loops work in desktops, but they would crash your browser. Fortunately, Emscripten solves this issue by giving us a function that makes our main_loop function be called periodically rather than continuously. Here are the parameters of this function:

emscripten_set_main_loop(
 mainloop, // callback function to main loop
 0, // frame rate (it is preferred to always use 0, requestAnimationFrame() will be used, making the animation smoother)
 1 // simulate infinite loop
);

Otherwise, if we are not compiling the game using Emscripten, then we can simply call the main_loop function while the game is running.

Alright! Emscripten also gives us a function to be called when the game is over: emscripten_cancel_main_loop() . Notice I use it in my quit_game function:

#ifdef __EMSCRIPTEN__
    emscripten_cancel_main_loop();
#endif

Boom, that’s it! We are ready to compile our game to WASM and run it in our browser!

Open your command-line interface tool, head over to the Snake’s game source code folder (a folder called src). As an example, here is how I would do it in using Linux:

$ cd snake

$ cd src

$ ls // displays all the files in the current directory, use it to make sure you are in the correct one

Now, let’s type the following command to compile the game:

$ emcc \
 -o app.html *.c \
 -Wall -g -lm \
 -s USE_SDL=2

That’s it. If everything went well, you should be able to see three new files inside the src folder: app.html , app.js , and app.wasm . That .wasm is our compiled WebAssembly code.

How can you see it in your browser? Pretty straightforward: type python -m SimpleHTTPServer 8080 to host a local web server and head to http://localhost:8080/app.html to see the Snake game up and running!

Simple as that — check out the Snake game running in your browser!

As a side note: of course, Emscripten is a large — and fortunately, well-documented — tool filled with oftentimes necessary complexities in order to make complex games and applications properly work in the browser. However, for the sake of this article’s length — as in, this is a mere introduction to Emscripten and its capabilities — we have only done the minimum necessary to make our simple Snake game run in the browser. If you wish to dive deep with Emscripten, don’t forget to take a look at its documentation!