Sorted arrays are a fundamental data structure that offers efficient search and insertion operations, making them valuable in various programming scenarios. In this article, we'll explore algorithms for searching and inserting elements into a sorted array using TypeScript. We'll delve into the intricacies of binary search and discuss how to maintain the array's sorted order while efficiently inserting new elements.

Binary Search Algorithm:

Binary search is a classic algorithm for finding the position of a target element within a sorted array. It follows a divide-and-conquer approach, repeatedly dividing the array in half until the target element is found or the search space is exhausted.

function binarySearchForInsertion(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;
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }    
    return left;
}

(Source: https://gazar.dev/algorithm/binary-search-algorithm)

Insertion into a Sorted Array:

Inserting a new element into a sorted array while maintaining its sorted order requires careful consideration. We can leverage binary search to find the correct position for insertion and then shift elements to accommodate the new element.

function insertIntoSortedArray(arr, num) {
    const insertionIndex = binarySearchForInsertion(arr, num);    
    const newArray = arr;
    newArray.splice(insertionIndex, 0, num);
    return newArray
}

insertIntoSortedArray([1,2,3,7,8,9],6) 
// [1, 2, 3, 6, 7, 8, 9]

Sorted arrays and the algorithms for searching and inserting elements into them are fundamental concepts in computer science and software engineering. By understanding and implementing efficient algorithms like binary search and insertion into sorted arrays, developers can optimize their code for performance and scalability. With TypeScript examples provided in this article, you're equipped to tackle search and insertion tasks in sorted arrays with confidence and proficiency.