Implementing Binary Search of an Array

Let's think about binary search on a sorted array. Many programming languages already provide methods for determining whether a given element is in an array and, if it is, its location. But we want to implement it ourselves, to understand how you can implement such methods. Here's an array of the first 25 prime numbers, in order:

Suppose we want to know whether the number $67$ is prime. If $67$ is in the array, then it's prime.

We might also want to know how many primes are smaller than $67$. If we find the position of the number $67$ in the array, we can use the position to figure out how many smaller primes exist.

The position of an element in an array is known as its index. Array indices start at $0$ and count upwards. If an element is at index $0$ then it is the first element in the array. If an element is at index $3$, then it has 3 elements which come before it in the array.

Looking at the example below, we can read the array of prime numbers from left to right, one at a time, until we find the number $67$—in the green box—and see that it is at array index $18$. Looking through the numbers in order like this is a linear search.

Once we know that the prime number $67$ is at index $18$, we can identify that it is a prime. We can also quickly identify that there are 18 elements which come before $67$ ...