# 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)
``````

### Assigned Tags

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.

Siva rama Krishna Pabbraju
Blog Post Author

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.

Siva rama Krishna Pabbraju
Blog Post Author

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.