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:

TypeScript
Copy to clipboard
1function recursiveBinarySearch(arr: number[], start: number, end: number, target: number): number {
2    // Base case: the search area is empty
3    if (start > end) return -1;
4
5    // Find the midpoint
6    let mid: number = Math.floor((start + end) / 2);
7
8    // Found the target
9    if (arr[mid] === target) return mid;
10
11    // If the target is less than the midpoint, search the left half
12    if (arr[mid] > target) {
13        return recursiveBinarySearch(arr, start, mid - 1, target);
14    }
15
16    // Otherwise, search the right half
17    return recursiveBinarySearch(arr, mid + 1, end, target);
18}

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

We can also visualize this search below:

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

Now, let's construct a binary search using a while loop in TypeScript:

TypeScript
Copy to clipboard
1function iterativeBinarySearch(arr: number[], target: number): number {
2    let start: number = 0;
3    let end: number = arr.length - 1;
4
5    while (start <= end) {
6        let mid: number = Math.floor((start + end) / 2);
7        if (arr[mid] === target) return mid; // Found the target
8        if (arr[mid] < target) {
9            start = mid + 1; // Search the right half
10        } else {
11            end = mid - 1; // Search the left half
12        }
13    }
14    return -1;
15}

In this version, the function does not call itself. Instead, it uses a while loop to accomplish the same goal.

Binary search reduces the input size by half at each step; thus, it takes $\log(n)$ steps to locate a target in an array of size n. Consequently, the time complexity of binary search is $O(\log n)$.

Both recursive and iterative approaches share the same time complexity ($O(\log n)$). The choice between them typically depends on specific problems, constraints, and personal preference.

Great job! You've grasped the core of binary search, implemented it in TypeScript, and explored its time complexity. Up next, we have practice exercises to help you master binary search. Happy coding, and see you in the practice session!