Hello everyone, I've lately been brushing up on my knowledge of data structures and algorithms. And I got the great idea to publish my notes as blogs. So, let's get started learning about binary search and code samples in javascript.
Introduction
Before we get into the binary search, let's talk about searching and types.
Linear Search
Binary Search, are the most used searching algorithm in programming.
Why is it necessary to search?
In programming and developing you generally encounter a situation where you have to find a user’s name by having a reference id in a database with millions of data.
When a user logs in to an app or website, searching for a user's name and email address in a database should not take long. If it does it will not be a good user experience
This is where searching algorithms come in to play.
Linear search
Linear searching is a simple searching algorithm that will search for the element in an array by traversing through every aspect of the array once.
So the time complexity is O(n).
Where O denotes big O notation, n denotes the number of elements in the array.
Here is the code example for it👇
function lineraSearch(arr, num) {
for (let x of arr) {
if (x === num) return arr.indexOf(num);
}
return -1;
}
let myarr = [
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 23, 3, 42, 13, 424, 23, 13, 24, 55, 55,
63, 3, 43, 65, 77, 87,
];
console.log(lineraSearch(myarr, 3));
//Output: 2
Binary Search
Now let’s talk about the binary search algorithm
Binary search only works on sorted arrays. This means the array elements have to be arranged in order of ascending or descending.
How does it work?
Binary search divides the array into half each time it iterates.
For example,
Here is a sample array containing elements that are arranged in ascending order.
First, we have to take 3 elements, the start of the array, the end of the array, and the middle of the array.
- Here, start = 0. End = index of the length of array -1. These are just index values not elements of the array.
To find the middle we have a formula, start + (end - start) / 2. So, middle = 3. And we have our target = of 18.
Now to proceed further we have 3 conditions to check,
If middle < target, then target lies on the right side of the array. Hence we can eliminate the left.
If middle > target, then target lies on the left side of the array. Hence we can eliminate the right.
If middle = target, the middle is the answer.
- Here are middle is 3, and the value is 9. Which is less than the target value, So eliminate the left side.
- Now we have our new start, end, and middle.
- Our new middle is 27 which is greater than the target. So eliminate the left side.
Now we have our last single element 18, which is equal to the middle. So now the middle is the answer. That’s it. Simple. Very easy.
Here is the code sample of Binary search in javascript,
function binSearch(arr, value) {
let start = 0; //Starting Point
let end = arr.length - 1; //Ending Point
while (start <= end) {
let middle = Math.floor(start + (end - start) / 2);
if (value < arr[middle]){ // Left side
end = middle - 1;
}else if (value > arr[middle]){
start = middle + 1; // Right side
}else{
return middle;
}
}
return -1;
}
let myarr = [
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 42, 424, 23, 13, 24, 55,
63, 43, 65, 77, 87,
].sort(function mySort(a,b){
return a-b;
});
console.log(binSearch(myarr, 55))
//Output: 17