JavaScript, best way to find the index interval in an array with given number

Question

I'm not sure if I describe the question right, So I'll give a simple example.
Let's say I have an array:

var array = [0, 1.1, 2, 2.4, 4, 4.6, 5];  

Given a number, 2.1
I want to find what index interval does it fall in. For this question, the answer will be 2,3.
Currently I have two ideas for this, first one is simple but definitely very slow, which is loop through the whole array and find where array[i-1] is less than 2.1 and array[i] is greater than 2.1.
Another way is, add 2.1 to the array, sort the array in ascending order, the answer will be the index of 2.1, and this index - 1.
Any other better suggestions?

Answer 1

You would do a binary search:

function binarySearch(array, el) {
    var m = 0;
    var n = array.length - 1;
    while (m <= n) {
        var k = (n + m) >> 1;
        var cmp = el - array[k];
        if (cmp > 0) {
            m = k + 1;
        } else if(cmp < 0) {
            n = k - 1;
        } else {
            return [k, k + 1];
        }
    }
    return [n, n+1];
}

var range = binarySearch([0, 1.1, 2, 2.4, 4, 4.6, 5], 2.3);

console.log(range);

The above code:

• Assumes that the array elements are all different and sorted ascending
• Returns a pair of indexes [i, i+1]
• Returns the pair of indexes such that array[i] <= el < array[i+1]
• If the given value is outside the range of the array, the output will be [-1, 0] when it is lower than the first array value, or [n-1, n] when it is greater than the last array value (n being the array's length).
• Has a O(log(n)) time complexity.