Binary Search
Tags: javascript, algorithms, webdev, beginners
Published: 2021-09-05 17:03:14

*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.

<hr/>
Let's see an example.

```javascript
 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.
```

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.

```javascript
  let start = 0;
  let end = list.length -1; // 9
```
Next, we need to set a middle point index and then compare its value to the item we're searching for.

```javascript
   let middle = Math.floor((start + end)/2); // 4
   if (list[middle] === itemToFind) return middle; 
```

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](https://i.ibb.co/1bhNkD3/best-case-scenario.png)

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. 
<hr/>
Let's start a new search and search for 30 this time. 
![Search for 30](https://i.ibb.co/0MsDPrR/searchfor30.png)

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.

```javascript
  if(middle > itemToFind){
    end = middle -1;
  } 
```
Then recalculate `middle` and check the new middle value.

```javascript
   if (list[middle] === itemToFind) return middle; 
   if(middle > itemToFind) end = middle -1; // 3
   middle = Math.floor((start + end)/2); // 1
```
![relocate the end point](https://i.ibb.co/BTdZgZd/relocate-the-end-point.png)

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`.

```javascript
  if(list[middle] < itemToFind){
    start = middle + 1;
  } 
```

Then recalculate `middle` and check the new middle value.

```javascript
   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
```

![relocate the start point](https://i.ibb.co/D8GT4nX/relocate-the-start-point.png)

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

![relocate the start point again](https://i.ibb.co/NLzfwSw/relocate-the-start-point-again.png)

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 `start`s where it `end`s. 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.

```javascript
// 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
}
```
(thank you for reading)

- [Introduction to Big O Notation](https://www.rithmschool.com/courses/javascript-computer-science-fundamentals/introduction-to-big-o-notation)
- [Binary Search Algorithm](https://www.gatevidyalay.com/binary-search-binary-search-algorithm/).
- [How to Calculate Binary Search Complexity](https://stackoverflow.com/questions/8185079/how-to-calculate-binary-search-complexity).