print-missing-one-number-in-sorted-list.js

// Utility functions
function populateNumbers(startNum, endNum, missingNum) {
    let numbers = [];
    for (let i = startNum; i <= endNum; ++i) {
        if (i !== missingNum) {
            numbers.push(i)
        }
    }

    return numbers;
}

function showNumbers(numbers) {
    let indexDesc = "";
    for (let i = 0; i < numbers.length; ++i) {
        indexDesc = `${indexDesc}, ${i}`;
    }
    indexDesc = indexDesc.substring(2);
    let desc = "";
    for (let i = 0; i < numbers.length; ++i) {
        desc = `${desc}, ${numbers[i]}`;
    }
    desc = desc.substring(2);
    console.log(`\n${indexDesc}\n${desc}\n`);
}

// Actual function(s) to show missing number
function showMissingNumber(level, numbers) {
    const count = numbers.length;

    if (count == 2) {
        console.log(`the last two numbers: ${numbers[0]}, ${numbers[1]}`);
        const missingNumber = numbers[0] + 1;
        console.log(`found at ${level + 1} step(s), missingNumber is ${missingNumber}`);
        return;
    }
    
    const middleIndex = Math.floor((count - 1) / 2);
    const numberAtMiddleIndex = numbers[middleIndex];
    const firstNumber = numbers[0];
    const lastNumber = numbers[count - 1];
    const halfLastNumber = Math.floor((lastNumber + firstNumber - 1) / 2);
    const desc = `count: ${count} middleIndex: ${middleIndex} numberAtMiddleIndex: ${numberAtMiddleIndex} lastNumber: ${lastNumber} halfLastNumber: ${halfLastNumber} `;
    console.log(desc);

    let subNumbers = [];
    if (halfLastNumber >= numberAtMiddleIndex) {
        subNumbers = numbers.slice(middleIndex, count);
        console.log(`missing number at right half`);
    } else if (halfLastNumber < numberAtMiddleIndex) {
        subNumbers = numbers.slice(0, middleIndex + 1);
        console.log(`missing number at left half`);
    }
    // showNumbers(subNumbers);
    showMissingNumber(level + 1, subNumbers);
}

// showMissingNumber(0, numList001);
// showMissingNumber(0, numList002);
const numList001 = populateNumbers(1, 9, 6);
const numList002 = populateNumbers(1, 15, 8);
const numList003 = populateNumbers(1, 5678901, 3);

showNumbers(numList001);
showMissingNumber(0, numList001);

showNumbers(numList002);
showMissingNumber(0, numList002);

// showNumbers(numList003);
showMissingNumber(0, numList003);

Using binary partition scheme to find one and the only missing number from sorted, ascending order numbers. And the missing numbers will be in any where except the first and the last position.