The Binary Search Algorithm
Tags: beginners, tutorial, learning, typescript
Published: 2024-03-11 22:11:20

## Intro

I recently took a data structures and algorithms course as part of my pursuit to learn lower level programming and computer science concepts. As the saying goes, the best way of solidifying your knowledge in something is to teach it, and since I've already filled my quota for boring my partner with coding talk for the month (probably the year), I thought I'd write a series of posts with some of the things I've learned. This is one such post.

## What is the Binary Search Algorithm

The binary search algorithm is an efficient way of returning the index of a given value in a sorted array. It has a worst-case time complexity of `O(log n)` where the element does not exist and a best-case time complexity of `O(1)` where the value we're searching for happens to be the first one we check!

## How does it work

The idea behind the binary search algorithm is to divide and conquer. First, we check the mid point in the array. If the mid point is equal to the value we're looking for, we return the value. Otherwise, we divide the array in half and continue to look in the appropriate half and repeat the process. Remember, this only works on a sorted array.

Let's write some pseudo-code where `v` = the `value` we're looking for to further this explanation:

```
lo = 0
hi = arr.length
mid = (lo + hi) / 2

while lo < hi
	if mid = v
		we found it!

	if mid > v
		hi = mid

	if mid < v
		lo = mid

we didn't find it :(

```

Here we have 3 pointers; `lo` (set to the 1st element of the array), `mid` (set to the middle point of the array) and `hi` (set to the length of the array). We check the value of `mid`; if `mid` is the value we're looking for, then we're done! If `mid` is greater than our value, this means that the value we're looking for (if it exists) will be in the left half of our array. At this point, we move our `hi` pointer down to where our `mid` pointer is and we start the process again. If, however, `mid` is **less** than our value, then we move our `lo` pointer **up** to where our `mid` pointer is, and we start the process again.

## How do we implement it

Here's some heavily commented Typescript:

```typescript
function binarySearch(
  haystack: number[], 
  needle: number
): number {
	let lo = 0;
	let hi = haystack.length;

	do {
		const mid = Math.floor((hi + lo) / 2);
		const v = haystack[mid];

		if (v === needle) {
			return mid;
		} else if (v > needle) {
			hi = mid;
		} else {
			lo = mid + 1; // we can exclude mid as we've already checked it
		}
	} while (lo < hi);

	return -1;
}
```

This implementation obviously uses a do-while loop, but you can get the job done with any kind of loop, really. Alternatively, this is a good place to use recursion. Here's what a recursive version might look like:

```typescript
function binarySearchRecursive(
	haystack: number[],
	needle: number,
	lo: number = 0,
	hi: number = haystack.length
): number {
	// Base case
	if (lo > hi) {
		return -1;
	}

	const mid = Math.floor((lo + hi) / 2);

	if (haystack[mid] === needle) {
		return mid; // We found it!
	}

	if (haystack[mid] < needle) {
        // recurse - search in the right half
		return binarySearchRecursive(haystack, needle, mid + 1, hi); 
	}

	if (haystack[mid] > needle) {
        // recurse - search in the left half
		return binarySearchRecursive(haystack, needle, lo, mid - 1); 
	}
}
```

### I think we're done here

That's it for our binary search algorithm. I hope you found it useful or, at least, interesting!