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
What is Binary Search
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
Add caption
Complexity
- Worst-case performance O(log n)
- Best-case performance O(1)
- Average performance O(log n)
- Worst-case space complexity
Should be:
ReplyDeleteif (nums[mid] === key) {
return mid;
}