Binary Search Algorithm in TypeScript

Binary Search is a widely used search algorithm that efficiently locates a target value within a sorted collection. It works by repeatedly dividing the search interval in half, narrowing down the possible locations for the target until it is found or the interval becomes empty.

Basic Implementation

Here is a basic implementation of Binary Search in TypeScript for a sorted array:

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

  while (low <= high) {
    const mid = Math.floor((low + high) / 2);

    if (arr[mid] === target) {
      return mid; // Target found
    } else if (arr[mid] < target) {
      low = mid + 1; // Discard the left half
    } else {
      high = mid - 1; // Discard the right half
    }
  }
  return -1; // Target not found
}

How Binary Search Works

Initial Setup

Set the low and high pointers to the first and last elements of the array, respectively.

Midpoint Calculation

Calculate the midpoint of the current search interval.

Comparison

Compare the element at the midpoint with the target value.

• If they are equal, the target is found, and the index is returned.

• If the element at the midpoint is less than the target, discard the left half of the interval.

• If the element at the midpoint is greater than the target, discard the right half of the interval.

Repeat

Repeat steps 2-3 until the target is found or the search interval is empty.

Time Complexity

The time complexity of Binary Search is O(log n), where 'n' is the number of elements in the array. This makes it significantly more efficient than linear search algorithms for large datasets.

Space Complexity

Binary Search has a space complexity of O(1) since it only uses a constant amount of additional memory for the low, high, and mid pointers.

Advantages of Binary Search

Efficiency

Binary Search is highly efficient for large datasets, especially compared to linear search algorithms.

Versatility

It can be applied to various types of sorted collections, including arrays and linked lists.

Optimization

Binary Search can be optimized for various scenarios, such as finding the first or last occurrence of an element.

Limitations of Binary Search

Sorted Data Requirement

The array must be sorted for Binary Search to work correctly.

Memory Overhead

Recursive implementations of Binary Search can have a higher memory overhead due to the call stack.

Conclusion

Binary Search is a powerful and efficient algorithm for finding a target value in a sorted collection. Its logarithmic time complexity makes it a popular choice for scenarios where quick search times are crucial, such as in large datasets or time-sensitive applications. Understanding Binary Search is fundamental to mastering search algorithms and computer science in general.