TypeScript: Implement Binary Search

1. Introduction

Binary search is a highly efficient algorithm used to find an element in a sorted list. Instead of searching the list sequentially as in linear search, binary search divides the list in half with each step, drastically reducing the number of comparisons needed.

2. Program Overview

We will implement the binary search algorithm that works on a sorted array. The algorithm works by repeatedly dividing in half the portion of the list that could contain the item until we've narrowed down the possibilities to just one.

3. Code Program

function binarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid;
        }
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }

    return -1;  // Return -1 if target is not found
}

// Test the function
const sortedArray = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19];
const targetElement = 15;
const index = binarySearch(sortedArray, targetElement);
if (index !== -1) {
    console.log(`Element ${targetElement} found at index: ${index}`);
} else {
    console.log(`Element ${targetElement} not found in the array.`);
}

Output:

Element 15 found at index: 7

4. Step By Step Explanation

1. The function binarySearch is declared which takes a sorted array arr and a target number target as its parameters.

2. We initiate two pointers: left and right to keep track of the portion of the array currently being searched.

3. Inside a while loop (which runs as long as left is less than or equal to right), we calculate the midpoint of the current segment.

4. If the middle element is equal to the target, we've found our element and return the mid index.

5. If the middle element is less than the target, it implies the target can only be present in the right half, so we update left to mid + 1.

6. Otherwise, the target can only be in the left half, so we update right to mid - 1.

7. If the loop completes and we haven't returned, the target isn't in the array. We then return -1 to signify that the element was not found.

8. We test the function using a sorted array and display the result.