Binary Search Algorithm using TypeScript
Binary search is a very fundamental algorithm in Computer Science. It powers BSTs (binary search trees) which form the basis of modern databases and immutable data structures. Binary search works very much the way humans intuitively search for a name in a yellow pages directory (if you have ever seen one) or the dictionary.
In this lesson we learn how to implement a Binary Search Algorithm using TypeScript / Javascript, and we describe the problem that it solves.
[00:00] We start off by creating a binary search function. This function takes an array of numbers and an element that we have to find within this array. The function will return the index of the element if it is found within the array. If you do not find the element within the array, we will simply return -1.
[00:22] To search for the element, one way to do that is to simply look through all the elements in the array until some element matches the element that we are searching for. If it matches, we return the index.
[00:43] In the worst case, the time complexity of this algorithm is O(n), since we have to access all the elements of the array. If you were to use the simple array prototype find index function, it would internally do a similar loop over all the elements of the array, and its time complexity will also be O(n).
[01:06] We can do better than this O(n) run time. These simple loop-based implementations fail to take advantage of the fact that the given array is sorted. In binary search, we recursively break down the problem into smaller ones. You will only search for the element within a given start and end range of the array. We initialize this range to be the entire array.
[01:34] Like all converging recursive algorithms, you will have a base case to terminate the recursion. For search, we can terminate if the problem space has gone below zero. In this case, we have not found our element yet, and we can return -1.
[01:52] Next, we simply divide the current problem space into two equal search spaces, refining the middle element of the current search subsection. If the middle element matches the element we are searching for, we have found our index, which is simply the middle.
[02:13] Else, we check if the element that we have to find is less than the middle element. If so, we recurse to the first half of the problem space as the element, if present, will have to be in that section. Otherwise, if the element is greater than the middle element, we recurse through the second half of the problem space, and that's it.
[02:43] This algorithm is called binary search because we divide the search problem into two, that is, binary sub-problems. Since in each recursive call we break down the search space in half, our problem size decreases exponentially, taking our worst case time complexity from O(n) to O(log n).