Binary Search in JavaScript🔥
Jaspal Singh
Posted on October 13, 2021
Hi everyone, I'm back with another blog in which we will understand binary search and implement it in JavaScript 🔥💜
Outline
- What is Binary Search?
- Condition to implement Binary Search.
- Key Points
- Use Cases
- Working of Binary Search
- Code Implementation of Binary Search
What is Binary Search?
Binary Search is a searching algorithm. It is more efficient than other searching algorithms such as Linear Search. Binary Search basically works on divide and conquer approach. That is after every search iteration the search space will get halved.
Condition to implement Binary Search
The main condition to implement the binary search is that your array/list should be sorted (either in increasing order or decreasing order).
Key points.
- It is more efficient than Linear Search.
- It has better time complexity that is O(logn)
- Cannot be used with unsorted array/list
Use Cases
- If you want to search for smallest or greatest number in array.
- To check whether the target number is present in array or not.
- You can even search for users' data if users are stored in sorted manner.
Working of Binary Search
- Take an sorted array and a number that you wish to search in array.
- We need two variables for start and end that are going to act as pointers
- Value of start initially will be 0.
- Value of end will be last index of the array (you can easily find it as array.length-1)
- Now you need to have another variable known as mid point. (You can calculate mid point as Math.floor((start+end)/2) )
- If the value at array[mid] is equal to your target number than it is your answer.
- If target number is great than array[mid] value then update your start variable to start = mid + 1
- If target number is less than array[mid] value then update your end variable to end = mid - 1
- Repeat it until start <= end.
Code Implementation.
function binarySearch(arr, num){
let start = 0;
let end = arr.length-1;
while(start <= end){
let mid = Math.floor((start + end) / 2);
if(arr[mid] == num){
return mid;
}else if(num > arr[mid]){
start = mid + 1;
}else if(num < arr[mid]){
end = mid - 1;
}
}
return -1; // if num is not present in the array
}
let studentIds = [11,12,15,19,23,45,54,91,100]
let result = binarySearch(studentIds, 100);
console.log(result);
PS:- Checkout This amazing resource to see the visualization of Binary Search
I hope I was able to deliver something good to you guys ☺. Feedback, suggestions, etc are always welcomed.
Have a fun and safe time and Thank you so much for dedicating your time to go through this blog ❤.
You can follow me on Twitter💜😅
"Let's Learn and Grow Together. Adios amigos/amigas hasta la proxima vez 💜☕"
Posted on October 13, 2021
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.