Skip to Content
Author's profile photo Siva rama Krishna Pabbraju

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

      5 Comments
      You must be Logged on to comment or reply to a post.
      Author's profile photo Bilen Cekic
      Bilen Cekic

      cool but why not using a proper toolkit library like Lodash to save some time ?

      _.find

      will do what you need.

      Author's profile photo Siva rama Krishna Pabbraju
      Siva rama Krishna Pabbraju
      Blog Post Author

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

      Author's profile photo Matthew Billingham
      Matthew Billingham

      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.

      Author's profile photo Siva rama Krishna Pabbraju
      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.

      Author's profile photo Matthew Billingham
      Matthew Billingham

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