Binary Search in Java Script

[krish469]

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

 

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)