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?

If the input array is alway sorted, then you can do a *binary search*, which takes O(log n) time unlike linear search which takes O(n). If not, the latter is the best you can do — meowgoesthedog, Aug 29 '17 at 09:45
Can you guarantee the order? Or could it be `arr = [1,1, 0, 4.6, 2]`? — evolutionxbox, Aug 29 '17 at 09:45
Looking through the array will definitely be faster than adding to it, sorting it, and then finding the index of the entry you added. — T.J. Crowder, Aug 29 '17 at 09:46
Sort the array and use the solution that you call "very slow". Only if you run into performance issues go for the binary search. Don't do premature optimization! — neuhaus, Aug 29 '17 at 09:46
Have a look at [this implementation](https://stackoverflow.com/a/14370245/1048572) — Bergi, Aug 29 '17 at 10:00

score 2 · Answer 1 · answered Aug 29 '17 at 20:09

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.

Mihai Alexandru-Ionut · Answer 2 · 2017-08-29T19:53:54.623

That can be achieved using binary insert algorithm.

Complexity:

It is in best case O(1) and in worst case O(N). Even if the Binary Insert in itself is only O(log(N)), the O(N) comes from the insert which will always be O(N) in the worst case if you insert a value at the beginning – you would have to push the rest of the values (N) to the end.

For instance, O(n) will be when you want to push 4 in follow array: let array=[3,6,9,10,20,21,23,24,26]

It takes O(log(N)) for search and O(n) for add.

How binary insert works:

var array = [0, 1.1, 2, 2.4, 4, 4.6, 5];
function binaryInsert(value, array, startVal, endVal){

 var length = array.length;
 var start = typeof(startVal) != 'undefined' ? startVal : 0;
 var end = typeof(endVal) != 'undefined' ? endVal : length - 1;
 var m = start + Math.floor((end - start)/2);
 
 if(length == 0){
  array.push(value);
  return;
 }

 if(value > array[end]){
  array.splice(end + 1, 0, value);
  return;
 }

 if(value < array[start]){
  array.splice(start, 0, value);
  return;
 }

 if(start >= end){
  return;
 }

 if(value < array[m]){
  binaryInsert(value, array, start, m - 1);
  return;
 }

 if(value > array[m]){
  binaryInsert(value, array, m + 1, end);
  return;
 }
}
let number=2.1;
binaryInsert(number, array,0,array.length);
console.log(array.toString());
let index=array.indexOf(number);
console.log(index-1,index);

score 0 · Answer 3 · answered Aug 29 '17 at 10:19

You can do using simple quicksort-style insertion function

var array = [0, 1.1, 2, 2.4, 4, 4.6, 5];
var element = 2.1;
function insert(element, array) {
  array.splice(locationOf(element, array) + 1, 0, element);
  return array;
}

function locationOf(element, array, start, end) {
  start = start || 0;
  end = end || array.length;
  var pivot = parseInt(start + (end - start) / 2, 10);
  if (end-start <= 1 || array[pivot] === element) return pivot;
  if (array[pivot] < element) {
    return locationOf(element, array, pivot, end);
  } else {
    return locationOf(element, array, start, pivot);
  }
}

console.log(insert(element, array));

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

3 Answers3