2
\$\begingroup\$

The task is to add a new number in the array of numbers sorted in ascending order.

So let's say the array is:

20,40,50,60

And the number to be inserted is 24,

the new array will be

[ 20, 24, 40, 50, 60 ]

The code for the above problem statement is as follows,

var myArray = [], 
    theNum = undefined;

// below function is used to capture the 
// commandline parameters for array and the
// number to be inserted
(function(){
    process.argv.forEach(function (val, index, array) {
        var idx = 0, ar = undefined;

        try{

            // get the commandline argument for 
            // array values 
            if(index === 2){
                myArray = myArray.concat(val.split(",").map(function(num){
                    return parseInt(num);
                }));    
            }

            // third index is the number to be searched.
            if(index === 3){
                theNum = parseInt(val)
            }

        }catch(e){
            console.log(e)
        }

    });
})();

console.log(" INSERT NUMBER ",theNum," in array ",myArray);
insertNum();

// main method to start
function insertNum(){

    var binarySearch = binarySearch; // methods
    var doInsertion = doInsertion; // methods

    // binary search the index position where the number can be inserted
    var index = binarySearch(myArray,0,myArray.length);

    console.log("Insert Number in position ",index);

    // insert new number at the searched index 
    // and move the following numbers to the immediate
    // next index position. Its a recursive call 
    doInsertion(index,theNum);

    console.log(" Array after new number insertion ",myArray);

    // binary search for index position,
    // where the new number be inserted
    function binarySearch(array,lowIndex,highIndex){
        console.log("LOW INDEX ",lowIndex," HIGH INDEX ",highIndex);
        var totalLenght = highIndex - lowIndex;
        var midIndex = parseInt(totalLenght/2);

        midIndex += lowIndex;

        if(lowIndex === highIndex){
            return lowIndex;
        }

        if(array[midIndex] === theNum){
            return midIndex;
        }else if(array[midIndex] < theNum){
            lowIndex = midIndex + 1;
        }else{
            highIndex = midIndex;
        }

        return binarySearch(array,lowIndex,highIndex);
    }// end of binary Search    


    // insert new number at the searched index 
    // and move the following numbers to the immediate
    // next index position. Its a recursive call
    function doInsertion(index,numToInsert){
        var temp = (index >= myArray.length) ? numToInsert : myArray[index];


        // once index position is more or equal to total array length, 
        // insert as new number in last position
        if(index >= myArray.length){ 
            myArray.push(temp);
        }else{
            myArray[index] = numToInsert;
            index++;

            // move the numbers ahead to next position
            // as if pushing to next position  
            doInsertion(index,temp);    
        }

    } // end of doInsertion

} // end of insertNum

In the above program I have used binary search to find the index position. and then I insert the new number at that position, and the rest I move forward.

The output of the program is as follows:

E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>node array02.js 1,4,6,8,10,13,18,23 6
 INSERT NUMBER  6  in array  [ 1, 4, 6, 8, 10, 13, 18, 23 ]
LOW INDEX  0  HIGH INDEX  8
LOW INDEX  0  HIGH INDEX  4
Insert Number in position  2
 Array after new number insertion  [ 1, 4, 6, 6, 8, 10, 13, 18, 23 ]

E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>node array02.js 1,4,6,8,10,13,18,23 5
 INSERT NUMBER  5  in array  [ 1, 4, 6, 8, 10, 13, 18, 23 ]
LOW INDEX  0  HIGH INDEX  8
LOW INDEX  0  HIGH INDEX  4
LOW INDEX  0  HIGH INDEX  2
LOW INDEX  2  HIGH INDEX  2
Insert Number in position  2
 Array after new number insertion  [ 1, 4, 5, 6, 8, 10, 13, 18, 23 ]

E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>node array02.js 1,4,6,8,10,13,18,23 14
 INSERT NUMBER  14  in array  [ 1, 4, 6, 8, 10, 13, 18, 23 ]
LOW INDEX  0  HIGH INDEX  8
LOW INDEX  5  HIGH INDEX  8
LOW INDEX  5  HIGH INDEX  6
LOW INDEX  6  HIGH INDEX  6
Insert Number in position  6
 Array after new number insertion  [ 1, 4, 6, 8, 10, 13, 14, 18, 23 ]

E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>node array02.js 20,40,50,60 24
 INSERT NUMBER  24  in array  [ 20, 40, 50, 60 ]
LOW INDEX  0  HIGH INDEX  4
LOW INDEX  0  HIGH INDEX  2
LOW INDEX  0  HIGH INDEX  1
LOW INDEX  1  HIGH INDEX  1
Insert Number in position  1
 Array after new number insertion  [ 20, 24, 40, 50, 60 ]

E:\RahulShivsharan\MyPractise\DesignPatternsInJavaScript>

Please do a code review; and please let me know how the code could have been implemented better.

Also let me know if my code has any drawbacks, and if so, how it can be improved.

\$\endgroup\$
0
1
\$\begingroup\$

Overall I think it looks pretty good as it is. I like the use of functional programming (i.e. using Array.map()) and the recursive functions.

There are a couple minor changes I would make:

parseInt radix

Pass the radix (usually 10 for base 10 numbers), i.e. the 2nd parameter of parseInt(), to ensure that input with leading zeros or other numbers will not be parsed contrary to your expectations (e.g. this scenario):

// get the commandline argument for 
// array values 
if(index === 2){
    myArray = myArray.concat(val.split(",").map(function(num){
        return parseInt(num, 10);
    }));    
}

// third index is the number to be searched.
if(index === 3){
    theNum = parseInt(val, 10)
}

... and similarly in the other spot where parseInt() is called.

Separate functions

I would move the nested functions (i.e. binarySearch and doInsertion) outside of insertNum, unless you like keeping it all tied up together?

function insertNum(){
    //implementation
}
function binarySearch(){
    //implementation
}
function doInsertion() { 
    //implementation
}

And what is the point of these two lines? I was able to remove them and still have the code function the same...

var binarySearch = binarySearch; // methods
var doInsertion = doInsertion; // methods

Typo

There appears to be a typo for the variable totalLenght - should it not be totalLength? For the sake of readability, I would correct that:

var totalLength = highIndex - lowIndex;

Small Consolidation

One place where 1 line of code could be reduced is in this block of doInsertion():

else{
    myArray[index] = numToInsert;
    index++;

    // move the numbers ahead to next position
    // as if pushing to next position  
    doInsertion(index,temp);    
}

The increment of index could be moved up to the array assignment:

myArray[index++] = numToInsert;

Alternatively, the prefix increment operator could be used on the recursive call:

doInsertion(++index,temp);    
\$\endgroup\$
2
\$\begingroup\$

I believe it is much better to keep things as simple and short as possible in order to make your code easy to read and maintain. Why don't you just create a function that adds a number to an array and then sort that array? Then you can call it with the number you want to add as parameter:

function addNumber(newNumber) {
  var numbers = [20,40,50,60];
  console.log('New number:', newNumber);
  console.log('Array before:' + numbers);

  numbers.push(newNumber);

  numbers.sort(compareNumbers);

  console.log('Array after:' + numbers);
}

function compareNumbers(a, b) {
  return a - b;
}

var result = addNumber(24);

// helper function
function showResult(result) {
  document.querySelector('#result').innerHTML = result;
}
<div id="result"></div>

\$\endgroup\$
2
  • \$\begingroup\$ Is the function "compareNumbers" really required ? number.sort() will also give me the desired solution, right ? \$\endgroup\$ – Rahul Shivsharan Jul 18 '17 at 9:14
  • \$\begingroup\$ It is required. According to Array.prototype.sort(), the default sort order is according to string Unicode code points. For example in [1, 10, 21, 2].sort(), 10 comes before 2, because '10' comes before '2' in Unicode code point order. You can read more here: developer.mozilla.org/en/docs/Web/JavaScript/Reference/… \$\endgroup\$ – krankuba Jul 18 '17 at 10:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.