Binary Search Algorithm

This one is a classic, and one every developer should know.

The Problem

Let's start with a leetcode problem for Binary Search:

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity.

So we start with a sorted array, your first instinct is perhaps to do something like this:

Honestly this was my first idea, and the most intuitive, but it's not very efficient, and only eliminates one possibility at a time.

There is a better way

The best way to do this is to create two pointers to keep track of. If we take the first pointer and put it at the beginning index, and the last pointer and put it at the end index (the length of array), we can then add the two and divide in half to find the middle value, and see if it is less than, or larger than our target, and since the array is sorted, we know all values before/after can be ignored, and adjust our pointer.

Time Complexity

Since every iteration, we go to the midway point and either find the target, or eliminate half the possibilities. So the loop will run as many time as the input array can be divided. Which is (log2 n)

Potential Overflow Issues with other languages

In python integers are unbound and can be infinitely large, but in other languages you may encounter an overflow issue.

Say the input array was very large, and the pointer integers were very close to the 32 bit integer max. (2^31), adding these pointers together would cause on overflow, giving us the wrong middle value.

Calculating midway point without adding pointers

Instead of adding the pointers together, we can use the distance between them. To get the distance between them, we can

This will give us half the distance between them, then take the and add the left index: