DEV Community

Hajar | هاجر
Hajar | هاجر

Posted on • Updated on

Binary Search

Binary Search is one of the fastest searching algorithms, especially when it comes to searching large (sorted) lists.
The main goal of Binary Search is to narrow down the area you're searching in as much as possible, which leads to reducing the steps you'd take to find an item.

When implementing Binary Search you should:
1- Assume that you're working on sorted lists -- otherwise, the search won't work.
2- Specify start and end points for where you should start and end searching.
3- Pick an item from the middle of the list and compare it to the item you're searching for. Based on that comparison, you should know if the item is found, or if you need to modify your start and end points and repeat the steps.


Let's see an example.

 function binarySearch(list, itemToFind){
   // some code to return the index of itemToFind
 }
  let list = [10, 21, 25, 30, 32, 35, 50, 52, 55, 60];
  let itemToFind = 32; 
  binarySearch(list, itemToFind) // should return the index of 32.
Enter fullscreen mode Exit fullscreen mode

To implement the code in binarySearch, we first need to set our start and end points. Since we need to cover the whole list, we need to specify our initial start point to be the first index of the list and end point to be the last index of the list.

  let start = 0;
  let end = list.length -1; // 9
Enter fullscreen mode Exit fullscreen mode

Next, we need to set a middle point index and then compare its value to the item we're searching for.

   let middle = Math.floor((start + end)/2); // 4
   if (list[middle] === itemToFind) return middle; 
Enter fullscreen mode Exit fullscreen mode

Since we are searching for an item that happens to be in the middle of the list, those few lines of code will return the index of itemToFind on the spot. This is called the best-case scenario of an algorithm -- your first guess is the correct answer.

Best case scenario of binary search

But of course, that rarely happens, so we need to cover the cases where we don't find our item in the middle of the list.


Let's start a new search and search for 30 this time.
Search for 30

Hmm, we calculated the middle point exactly as before, but unfortunately, we didn't find 30 there.

Now, we know that the middle item does not equal itemToFind. But is it greater or less than itemToFind?

We found 32, which is greater than 30. So what does that mean?

Since list is sorted, that means that itemToFind must be somewhere between start and middle.

Next step: relocate the end point of the search to narrow the search window.

  if(middle > itemToFind){
    end = middle -1;
  } 
Enter fullscreen mode Exit fullscreen mode

Then recalculate middle and check the new middle value.

   if (list[middle] === itemToFind) return middle; 
   if(middle > itemToFind) end = middle -1; // 3
   middle = Math.floor((start + end)/2); // 1
Enter fullscreen mode Exit fullscreen mode

relocate the end point

The middle item is now 21. It doesn't equal 30 so we can't return its index. It's not greater than 30, so relocating end to narrow the search area is not an option. However, we can relocate start. Because at this point, if the item exists, it must be somewhere between middle and end.

  if(list[middle] < itemToFind){
    start = middle + 1;
  } 
Enter fullscreen mode Exit fullscreen mode

Then recalculate middle and check the new middle value.

   if(list[middle] === itemToFind) return middle; 
   if(list[middle] > itemToFind) end = middle -1; // 3
   if(list[middle] < itemToFind) start = middle + 1; // 2
   middle = Math.floor((start + end)/2); // 2
Enter fullscreen mode Exit fullscreen mode

relocate the start point

We find 25. It's still less than 30. So we relocate start, calculate middle, and check again.

relocate the start point again

Finally, middle is pointing to the item we're searching for. However, that has happened after we have exhausted all our searching options, where our search window starts where it ends. This means that we've found our item at the worst-case scenario of the algorithm -- your last chance of guessing is the correct answer.

Note: The worst-case scenario also happens if itemToFind doesn't exist in list.

One last thing I should mention about Binary Search is that it has O(log n) time complexity, which means it takes log n time to find an item in the worst-case scenario.

// final implemtation
function binarySearch(list, itemToFind) {
  let start = 0;
  let end = list.length - 1;
  while (start <= end) {
    let middle = Math.floor((start + end) / 2);
    if (list[middle] === itemToFind) return middle;

    if (list[middle] > itemToFind) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
  }
  return -1; // not found
}
Enter fullscreen mode Exit fullscreen mode

(thank you for reading)

Discussion (12)

Collapse
stefnotch profile image
stefnotch

Nice explanation and congratulations on presenting an actually correct variant of binary search. 🚀

Since I believe that anything can be improved, no matter how nice it is, here is some feedback:
Issues

  • No parameters. list and itemToFind should very much be parameters that are passed to the function
  • Usage of parseInt. It's really not needed and it just causes a performance overhead.
  • (start + end) / 2 isn't ideal either, since with large enough arrays, this can cause some overflowing/rounding. The improved variant is start + ((end - start ) / 2) Might be interesting to note
  • An alternative to return -1 is return -start. Then, the negative return value would point at the smallest element that's >= itemToFind. And that's pretty useful when one wants to insert a new element.
Collapse
hajarnasr profile image
Hajar | هاجر Author

Thank you so much for your feedback @stefnotch . 😀
I fixed the no-parameters issue but am curious, why do you think that parseInt isn't needed here? Aren't we using it to avoid having fractions in the middle index? 🤔

Collapse
stefnotch profile image
stefnotch

I see, I missed that detail!

Although, parseInt is not designed for that. It's purpose is to turn a string (text) into a number. If the intention is to chop off the fractional part, then Math.floor is the standard function to use.
e.g. start + Math.floor((end - start) / 2)

Collapse
aminmansuri profile image
hidden_dude

I like your idea of returning -start.

Collapse
segdeha profile image
Andrew Hedges

Great explanation of this kind of search! Nice work, Hajar!

Collapse
hajarnasr profile image
Hajar | هاجر Author

Thank you so much for reading, Andrew. I appreciate it. 🌹

Collapse
mahmoudessam profile image
Mahmoud EL-kariouny

thanks :)

Collapse
peter_brown_cc2f497ac1175 profile image
Peter Brown

Thank for taking the time to right a legit article instead of all the fluff that so many others produce.

Collapse
hajarnasr profile image
Hajar | هاجر Author

Thank you, Peter. You're so kind. 😊

Collapse
hamodey85 profile image
Mohammed Almajid

perfect explanation

Collapse
hajarnasr profile image
Hajar | هاجر Author

Thank you for reading. :)

Collapse
kuw13 profile image
kuw13

Can you please contact me at
kuw13@yahoo.com

Mass