Introduction to Advanced Binary Search Problems in TypeScript

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.

Problem 1: Searching in a Bitonic Array
Efficient Approach Explained

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.

function findPeak(arr: number[]): number {
    let start: number = 0, end: number = arr.length - 1;

    // Search for the peak index
    while (start < end) {
        const mid: number = Math.floor((start + end) / 2);
        if (arr[mid] > arr[mid + 1]) {
            end = mid; // Peak is to the left
        } else {
            start = mid + 1; // Peak is to the right
        }
    }
    return start; // The peak index is found
}
Solution Building: Searching the Target

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

function binarySearchInBitonicArray(arr: number[], target: number): number {
    const peak: number = findPeak(arr);

    // Binary search on the ascending sub-array
    let start: number = 0, end: number = peak;
    while (start <= end) {
        const mid: number = Math.floor((start + end) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] < target) start = mid + 1;
        else end = mid - 1;
    }

    // Binary search on the descending sub-array
    start = peak + 1, end = arr.length - 1;
    while (start <= end) {
        const mid: number = Math.floor((start + end) / 2);
        if (arr[mid] === target) return mid;
        else if (arr[mid] > target) start = mid + 1;
        else end = mid - 1;
    }
    return -1; // If the target is not found in either sub-array
}

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.

Sign up
Join the 1M+ learners on CodeSignal
Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal