Binary search

Overview

In computer science, there are some problems that may repeat themselves in the daily job of a software engineer. one of the most common is searching through a collection of items, and a common approach to this kind of problem is the binary search implementation.

Why

When we are heading to solve any problem it is indeed important to know the rational reasons to approach the problem in one-way over another. think about a situation where you want to find a certain book in the library (Where all the books are already sorted alphabetically) you can go through the "array" of books one by one from the letter A until you get to the letter Z, you will finally find the book but does this kind of "searching algorithm" is efficient? well in computer science this kind of searching is called a linear search where you pass through any item in the array until you find your target, which is called also the time complexity of O(n), but what if our n is a million items or one billion? this kind of solution is very inefficient. with that in mind, we can use our binary search algorithm.

Conceptual understanding of binary search

The main concept of binary search is achieving a time complexity of O(log(n)) which is the opposite of exponential time complexity, where with each iteration we will shrink our array by half our solution becomes more efficient in the manner of time complexity. our implementation of the algorithm goes this way:

• Set a variable of the starting position of our array with an initial value of 0.
• Set a variable of the end position of our array with an initial value of the array length minus 1. (Minus 1 because we index from 0)
• Do a while loop that will fire while the "start" is smaller than the "end"
• Get the middle index in the array and save it as a variable (Using the start and end positions)
• Check if the value of the middle index item is the target, if it does we return the position
• If the value is less than the target, that means we can get rid of the left side of the array and declare the starting position of the array from the middle position and above excluding the middle.
• If the value is greater than the target, that means we can get rid of the right side of the array and declare the ending position of the array from the middle position and below excluding the middle.

Conclusions

Implementing binary search is a key concept to understand, even though in most cases linear search with a simple "for loop" can get the wanted result but when we are dealing with a huge amount of data this kind of solution becomes somewhat inefficient. here is below an actual code implementation of binary search written in TypeScript.