# Binary Search in Java Script

Recently, I have come across a situation where I need to consume data in Json format from multiple APIs. Here, I need to loop on first set of records and read second set of records for a particular key.

As we know, Loop inside loop will be huge performance issue, so I have searched for binary search concept and its implementations in javascript. I have found couple of links which has shared enough information for me to get started.

https://stackoverflow.com/questions/22697936/binary-search-in-javascript

https://medium.com/employbl/implement-linear-and-binary-search-algorithms-with-javascript-2149997588f0

After going through these links, i have found my solution and wanted to share the same.

Below is the code, we can execute this code in any console.

``````//Binary Ssearch Function
//arr - Array of values - Json
//target - To be matched value
function onBinarySearch(arr, target) {
let left = 0;
let right = arr.length - 1;

while (left <= right) {

//Calculate middle record
const mid = left + Math.floor((right - left) / 2);

//check if middle record is matched with target value
//here "id" is  one of the field which we trying to match its value
if (arr[mid].id === target) {

//Check if any other record which is less than mid has same value as target
var new_mid = mid
while(true){
new_mid --;

if(new_mid < 0){
return new_mid + 1;
} //if(new_mid < 0)

if(arr[new_mid].id !== target){
return new_mid + 1;
}  //if(arr[new_mid].id !== target)

} //while(true)

} //if (arr[mid].id === target)

//If target is less than mid value then move towards left
if (arr[mid].id < target) {
left = mid + 1;
} //if (arr[mid].id < target)

//If target is greater than mid value then move towards right
else {
right = mid - 1;
} //else
}
return -1;
}

//Field "Newname" in Json1 will be filled from field "Name" from Json2
//based on common field "id"
var json1 = [{
"name": "user1",
"id": 'F1044',
"newname": '',
},
{
"name": "user2",
"id": 'F1049',
"newname": ''
},
{
"name": "user3",
"id": 'EEDMSETTLUNIT03',
"newname": '',
}];

var json2 = [{
"name": "user1",
"id": 'F1044'
},
{
"name": "user2",
"id": 'EEDMSETTLUNIT03'
},
{
"name": "user3",
"id": 'EEDMSETTLUNIT03'
},
{
"name": "user4",
"id": 'EEDMSETTLUNIT03'
},
{
"name": "user5",
"id": 'F1049'
},
{
"name": "user6",
"id": 'F1049'
},
{
"name": "user7",
"id": 'F1044'
},
{
"name": "user8",
"id": 'F1044'
},
{
"name": "user9",
"id": 'F1049'
},
{
"name": "user10",
"id": 'F1044'
}];

//Sort json2 so that we can use binary search function on json2
json2.sort(function(a, b){
var x = a.id.toLowerCase();
var y = b.id.toLowerCase();
if (x < y) {return -1;}
if (x > y) {return 1;}
return 0;
});

//Fetch length of json2 in "n"
var n = json2.length

//For each record in json1, get all names from json2 for same id
//and update newname of json1
for(j = 0; j < json1.length; j++){

//fetch index of json2 for which json1[j] id is matched
var k = onBinarySearch(json2,json1[j].id)

//k = -1 =>id is not matched
if(k != -1){

//loop for json2 records from index k
while(k != -1){

if(k <= n - 1){

if(json1[j].id == json2[k].id){
json1[j].newname += json2[k].name + ' ';
k++;
} //if(json1[j].id == json2[k].id)

else{
k = -1
}//else

}//if(k <= n - 1)

else{
k = -1
}//else

}//while(k != -1)

}//if(k != -1)

}//for(j = 0; j < json1.length; j++)

//Print values of json1 and json2 to console
console.log(json1,json2)
``````

You must be Logged on to comment or reply to a post.
• cool but why not using a proper toolkit library like Lodash to save some time ?

``_.find``

will do what you need.

• Thanks Bilen, I am not aware of this library will look into it.

• In the same way that SORT… and READ … BINARY SEARCH is unnecessary in ABAP when you have HASHED tables, you can have hash maps in JS. https://www.npmjs.com/package/hashmap

This is classic case of looking for how to do thing technical rather than thinking about the problem you’re trying to solve. Your need is not “how to do a binary search”, it’s how to perform a lookup in a dataset in the most efficient way.

• Thanks Matthew, I was not aware of Hashmap. I will look into it. My case will work with multiple fields in json file. Hope Hashmap covers that.

• If not that hashmap doesn’t cover it, then something else will. Hashmaps are usually more efficient than binary searches.