Ahmed Essam
Ahmed Essam's blog

Ahmed Essam's blog

Binary Search

Binary Search

Ahmed Essam's photo
Ahmed Essam
·Mar 20, 2022·

2 min read

In this article, we will discuss a famous algorithm which is the Binary Search. First, let's talk about the importance and essentials of this algorithm. Binary Search is given a sorted list and a value to search for, and again it must be a sorted list else the algorithm won't work. In case you are wondering the difference in performance between it and the normal searching way, there is a huge difference as normal searching will check for every value in the list which will take a lot of time and can even freeze your application when dealing with extensive lists.

The way the algorithm work is that it will take a range from the list then it will get the middle value of this range and check if the guessed value (middle term) equals the value we are searching for, if not it will shrink its range and check again and it will be repeated over and over until it finds the value.

If you are familiar with algorithms, the Binary search has a Logarithmic time complexity O(log n), and the normal searching algorithm has a linear time O(n).

Without any further ado, let's jump into coding. (we will be covering it with JavaScript for this article).

function binary_search(list, value) {

let low = 0; //  initial starting value
let high= list.length - 1;  // last value in the list 


while (low <= high) {  // checking that the left is not a single value

  let mid = Math.round( (high  + low) / 2 ) // the middle value;
  let guess = list[mid];

   if (guess == item) {
      return mid;
    } else if (guess > item) {
      high = mid - 1; // shrink for the end
    } else {
      low = mid + 1; // shrink for the beginning
    }

}

  // if no matches were found
  return null

}

Hope you found this article useful. Leave me your thoughts about the algorithms and if you have ever used it

Did you find this article valuable?

Support Ahmed Essam by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this