# Binary Search in Javascript

In this article, I am going to show you the importance of Binary Search and how to implement using Javascript. There are many articles out there talking about this algorithm, so I am not going to repeat it here. 
<br>
It is also known as **logarithmic search** because of the time complexity **O(log n) **.
If you don't what time complexity means, you can check out  [this article](https://medium.com/analytics-vidhya/big-o-notation-time-complexity-in-javascript-f97f356de2c4)  to know more. In short, the time complexity is a way to find the runtime of an algorithm.

In a practical scenario, suppose you have an app with users with names from A to Z, then you are going to use a binary search algorithm starting from the middle to find the user name. By using this algorithm, you could find an element with 7 guesses from 100 items length array and that's the power of binary search. 

### Things to note

- Array needs to be sorted.
- After each search, the algorithm will divide the array in half. 


For writing Javascript snippets, I use  [RunJS](https://runjs.app/)  which is really easy to use. If you are doing coding practices, then I would suggest writing on a paper first and then Text Editor (NOT IDE). 

### Checking if an element exists in a sorted array

1) **In-built function **

```
let arr = [2, 3, 5, 7, 10, 20 ,22, 25, 30, 33, 34, 37, 40, 46];
let searchVal = 10;

//To check if element is present or not
console.log(arr.includes(10))  // true

//To print search value index
console.log(arr.indexOf(10))  // 4``` 

Check  [this one](https://medium.com/@nathanbell09/binary-search-vs-indexof-63651f91acb7)  as it talks about Binary Search vs indexOf.

2) **Binary Search**
  

```
function binarySearch(arr, number) {
  let start = 0;   // start index
  let end = arr.length - 1;  //array length

 //LOOP until start index great than end index
  while (start <= end) { 
    let mid = Math.floor((start + end) / 2); //middle index
    if (arr[mid] == number) return true; 
    else if (number < arr[mid]) {
      end = mid - 1;
    } else if(number > arr[mid]) {
      start = mid+1;
    } 
  }
return false;
}
//Driver code
let arr = [1, 3, 4, 6, 12, 35, 40, 45, 57];
let number = 45;
binarySearch(arr, number);
``` 
As you can see from the code, 

- You will have three variable *start*, *mid* & *end* index. 
- *Math.floor* is used to remove floating values. **JS Tip:** you could also use ~~((start + end) / 2)

**Useful animation**
![1_EYkSkQaoduFBhpCVx7nyEA.gif](https://cdn.hashnode.com/res/hashnode/image/upload/v1621581724483/btYKULOU-.gif)

### Next Step
Find the square root of a large number in O(logn) time. For example, find square root of *121*.
**Hint**: Use binary search.

If you need to add anything or found anything to update please use the comment
below.

### Useful Readings
 
- [https://stackoverflow.com/a/542509/1133629](https://stackoverflow.com/a/542509/1133629) 
-  [https://www.geeksforgeeks.org/binary-search/](https://www.geeksforgeeks.org/binary-search/) 


## Join our Mailing List







%%[convertkit]