Skip to Content

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)

 

To report this post you need to login first.

5 Comments

You must be Logged on to comment or reply to a post.

  1. 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.

    (1) 

Leave a Reply