I am attempting to add a number into an already sorted array of unique numbers in such a way that the resulting array remains sorted. The steps I plan to take are as follows:
- Divide the array into halves until each half consists of either 1 element or 2 elements
- If there are 2 elements: if
numberfalls between the 2 elements, return[element1, number, element2], otherwise return[element1, element2] - If there is 1 element: if
numbermatcheselement, return[number, element], otherwise return[element]
I believe that a recursive solution should break down the array until number can be added next to its counterpart or inserted between a lower and upper bound. Then the new array is assembled going back up the call stack. (I am aware this approach may not work correctly if number is less than the lowest element or greater than the highest)
This is the code snippet I have written:
function insertNum(num, sortedSet){
var returnValue;
console.log(`sortedSet:${sortedSet}`);
if (sortedSet.length==0){
return [num];
}
if(sortedSet.length>1){
console.log('length greater than 1');
output = splitInHalf(sortedSet);
if(num>output.first[output.first.length-1]&&num<output.second[0]){
console.log(`${num} belongs between`);
return output.first.concat([num]).concat(output.second);
}
else{
return insertNum(num, output.first).concat(insertNum(num, output.second));
}
}
else{
if(num == sortedSet[0]){
returnValue = [num, sortedSet[0]];
console.log(`returning append:${returnValue}`);
return returnValue;
}
else{
return sortedSet;
}
}
}
function splitInHalf(sortedSet){
halflength_floor = Math.floor(sortedSet.length/2);
halflength_ceil = Math.ceil(sortedSet.length/2);
console.log(`halflength_floor:${halflength_floor}`);
console.log(`halflength_ceil:${halflength_ceil}`);
first = sortedSet.slice(0, halflength_floor);
second = sortedSet.slice(halflength_floor);
console.log(`first:${first}`);
console.log(`second:${second}`);
var output = [];
output.first = first;
output.second = second;
return output;
}
console.log(insertNum(7, [2,3,5,6,8]));
The current output obtained is:
sortedSet: 2, 3, 5, 6, 8
length greater than 1
halflength_floor: 2
halflength_ceil: 3
first: 2, 3
second: 5, 6, 8
sortedSet: 2, 3
length greater than 1
halflength_floor: 1
halflength_ceil: 1
first: 2
second: 3
sortedSet: 2
sortedSet: 3
sortedSet: 3
[ 2, 3, 3 ]
The issue arises because the following outputs are never observed:
sortedSet: 5
sortedSet: 6, 8
This leads me to suspect that in the initial invocation of:
insertNum(num, first).concat(insertNum(num, second))
where the arguments should be:
insertNum(7, [2, 3]).concat(insertNum(7, [5, 6, 8])
only the first insertNum() call is executing, while the other insertNum() within concat() does not trigger. Why is this happening?