Binary Search in TypeScript

Greetings! Today, we're exploring binary search, an efficient algorithm that pinpoints elements in a sorted list. It's analogous to locating a house number on a long street — rather than starting from one end, you begin in the middle and, based on whether the house number is higher or lower, you search the right or left half of the list.

We'll learn to:

1. Understand binary search.
2. Implement binary search using recursion and iteration in TypeScript.
3. Analyze the time complexity of binary search.

Binary search is a classic example of the divide-and-conquer strategy. It starts by examining the middle element of a sorted list. If the middle element matches the target, you're done! If not, binary search eliminates half of the remaining elements based on whether the target is greater or smaller than the middle element. This process repeats until the target is found or the list is exhausted.

Let's implement binary search in TypeScript using recursion. Here's the code, accompanied by detailed comments:

function recursiveBinarySearch(arr: number[], start: number, end: number, target: number): number {
    // Base case: the search area is empty
    if (start > end) return -1;

    // Find the midpoint
    let mid: number = Math.floor((start + end) / 2);

    // Found the target
    if (arr[mid] === target) return mid;

    // If the target is less than the midpoint, search the left half
    if (arr[mid] > target) {
        return recursiveBinarySearch(arr, start, mid - 1, target);
    }

    // Otherwise, search the right half
    return recursiveBinarySearch(arr, mid + 1, end, target);
}

This function calls itself recursively, gradually narrowing down the search area until it finds the target.

We can also visualize this search below:

[ 1 2 3 4 5 6 7 8 9 ] <- we want to find 3
|                   | <-the lines are the limits of our search
[ 1 2 3 4 5 6 7 8 9 ]
|       ^           | <- mid point is on 4
[ 1 2 3 4 5 6 7 8 9 ] <- 4 is larger than 3, ignore the right
|         |           <- our search area is cut in half!
[ 1 2 3 4 5 6 7 8 9 ]
|   ^    |            <- mid point is now 2
[ 1 2 3 4 5 6 7 8 9 ] <- 2 is smaller than 3, ignore the left
  |      |            <- our search area is cut again!
[ 1 2 3 4 5 6 7 8 9 ]
  |   ^  |            <- midpoint is now 3, out target!