How to implement binary search in typescript/JavaScript

Binary search is a search algorithm that finds the position of a value within an ordered array of data. Given a sorted array and a target value, binary search breaks the array into two partitions and compares the target to the middle element in each partition. If it is equal to the target then it’s in one of these two positions, otherwise, binary search can conclude that the target value will be in one of the two partitions still to be searched.
In this article, I will show you how to implement Binary Search in typescript.
By the end of this post you will learn

  • What is Binary Search?
  • How to implement Binary search algorithm in JavaScript or TypeScript
  • Complete source code implementations of binary search in JavaScript

Binary search compares the target value to the middle element of the array. If they are not equal, the half in which the target cannot lie is eliminated, and the search continues on the remaining half, again taking the middle element to compare to the target value, and repeating this until the target value is found. If the search ends with the remaining half being empty, the target is not in the array.


Pseudo Code

export function binarySearch(nums: Array<number>, key: number): number {
  let low = 0;
  let high = nums.length - 1;
  while (low <= high) {
    let mid = Math.floor((low + high) / 2);
    mid;
    if (nums[mid] === key) {
      return mid + 1;
    }
    if (key > nums[mid]) {
      low = mid + 1;
    } else {
      high = mid - 1;
    }
  }
  return -1;
}

Animation

How to implement binary search in typescript/JavaScript

Add caption

Complexity

  • Worst-case performance O(log n)
  • Best-case performance O(1)
  • Average performance O(log n)
  • Worst-case space complexity

Further reading

Wikipedia

1 Comments

Please do not post any spam link in the comment box😊

Previous Post Next Post

Blog ads

CodeGuru