Greetings, curious minds! Today, we'll explore binary search applications that transcend basic searching. We'll apply binary search to complex data structures, such as bitonic arrays and rotated sorted arrays, to find specific elements efficiently.

Consider a bitonic array as a numerical sequence simulating the trajectory of a roller coaster — first, it rises to a peak, then descends. For example, consider the array [1, 2, 3, 4, 5, 3, 1]: its first part ascends, and the last descends, making it bitonic. Your goal is to find a value in such an array. You might walk the entire path, which is exhaustive and represents our naive approach with a time complexity of $O(n)$. Our aim today is a more efficient method.

To apply binary search, we first locate the peak of the array, then perform binary search on either side of the peak: one for the increasing sub-array and one for the decreasing sub-array.

TypeScript
Copy to clipboard
1function findPeak(arr: number[]): number {
2    let start: number = 0, end: number = arr.length - 1;
3
4    // Search for the peak index
5    while (start < end) {
6        const mid: number = Math.floor((start + end) / 2);
7        if (arr[mid] > arr[mid + 1]) {
8            end = mid; // Peak is to the left
9        } else {
10            start = mid + 1; // Peak is to the right
11        }
12    }
13    return start; // The peak index is found
14}

Now, let's perform a targeted binary search on sub-arrays.

TypeScript
Copy to clipboard
1function binarySearchInBitonicArray(arr: number[], target: number): number {
2    const peak: number = findPeak(arr);
3
4    // Binary search on the ascending sub-array
5    let start: number = 0, end: number = peak;
6    while (start <= end) {
7        const mid: number = Math.floor((start + end) / 2);
8        if (arr[mid] === target) return mid;
9        else if (arr[mid] < target) start = mid + 1;
10        else end = mid - 1;
11    }
12
13    // Binary search on the descending sub-array
14    start = peak + 1, end = arr.length - 1;
15    while (start <= end) {
16        const mid: number = Math.floor((start + end) / 2);
17        if (arr[mid] === target) return mid;
18        else if (arr[mid] > target) start = mid + 1;
19        else end = mid - 1;
20    }
21    return -1; // If the target is not found in either sub-array
22}

The binarySearchInBitonicArray function locates a target in a bitonic array by first finding the peak. It then performs a binary search on the ascending part up to the peak and, if the target is not found, on the descending part. It returns the index if found, otherwise -1.

Imagine you have a shuffled deck of cards that needs to be reordered. That could be represented with a rotated sorted array. For example, if we rotate the array [1, 2, 3, 4, 5], we could get [3, 4, 5, 1, 2]. You could check each element, one by one, to find the lowest, which is our naive approach with a time complexity of $O(n)$. Or, we could use binary search for a more efficient find.

For our advanced approach by adjusting our binary search logic to this context.

We apply our strategy to solve this problem.

TypeScript
Copy to clipboard
1function findMinimumInRotatedSortedArray(arr: number[]): number {
2    let start: number = 0, end: number = arr.length - 1;
3
4    // Binary search to find the rotation point
5    while (start < end) {
6        const mid: number = Math.floor((start + end) / 2);
7        if (arr[mid] > arr[end]) {
8            start = mid + 1; // Rotation point is to the right
9        } else {
10            end = mid; // Rotation point could be to the left
11        }
12    }
13
14    return arr[start]; // The minimum element is found
15}

The findMinimumInRotatedSortedArray function uses binary search to locate the minimum element in a rotated sorted array. It adjusts the search range based on whether the middle element is greater than the last element, iterating until start indicates the minimum element, which is returned.

Mastering binary search in TypeScript is akin to mastering quick decision-making in a labyrinth; each choice is a pivot leading to a more efficient exit. Today, you have learned to tackle complex problems using binary search techniques with TypeScript. These tasks, which at first glance seemed intricate, are readily solvable using the power of TypeScript's features, ensuring efficient and reliable solutions.

With this enhanced understanding, we now advance to practice exercises. Apply the binary search principles you've learned to navigate through and solve the forthcoming challenges. Happy coding!