Discussion on: Daily Challenge #60 - Find the Missing Letter

I really like this question. Though the naive solution would be to just iterate through the array and print the missing letter. Resulting in O(n) complexity. We can modify the binary search algorithm to reduce the complexity to O(logn).

The logic is simple. Just split the array into two equal parts and find the difference of ASCII code of char at the start and end of each part. The part where the difference is greater, is the one where the missing letter lies. Now recursively call the same function on the part where the missing letter lies.
The base condition would be an array with length 2. In this case, the missing letter is just after the first char.

However, there are a few edge cases to consider.
1. What will be our mid in case of array with odd length?
Well, it is easy, include the mid element in both array.
mid = arr.length/2

2. What will be our mid in case of array with even length?
We need to split our array into two equal halves, otherwise, the one with smaller length might have the missing letter. In which case both the difference will be equal. So, to solve this, we will have 2 mids.
mid1 = (arr.length - 1) / 2
mid2 = arr.length / 2
This is also convenient as in case of odd length, mid1 will be equal to mid2.
For example, let's consider an array of length 5.
mid1 = (5 - 1) / 2 = 2
mid1 = 5 / 2 = 2 (integer division)
So, we don't need to introduce a branch in our code for this! 🎉

3. What if the missing number is exactly in the center?
Well, in this case, the difference between both parts will be equal. We need to handle this as a special case.

4. What if splits results in an array with length less than 2?
This will only happen when an array of length 3 was divided into two parts and the missing letter is just after the first letter. For this, we just need to adjust our base condition. We change it from 2 to <= 2. Again not introducing a branch in our code.

Final code:

function findMissingLetter(arr) {
    // Base condition
    // When array length is less than 2 then the second letter is missing.
    if (arr.length <= 2) {
        return String.fromCharCode(arr[0].charCodeAt(0) + 1);
    }

    const midPos1 = Math.floor((arr.length-1)/2);
    const midPos2 = Math.floor(arr.length/2);
    const start = arr[0].charCodeAt(0);
    const mid1 = arr[midPos1].charCodeAt(0);
    const mid2 = arr[midPos2].charCodeAt(0);
    const end = arr[arr.length - 1].charCodeAt(0);

    if (mid1 - start > end - mid2) {
        return findMissingLetter(arr.slice(0, midPos1));
    } else if (mid1 - start < end - mid2) {
        return findMissingLetter(arr.slice(midPos2));
    } else {
        // If both split are equal then the letter missing is at the center.
        return String.fromCharCode(mid1 + 1);
    }
}

Try / Fork it ideone.com/YXz3HL