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.