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

Question

I am not sure if I am describing the question correctly, so I will give a simple example.
Let's say I have an array:

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

Given the number, 2.1
I want to find what index range it falls into. On this question, the answer will be 2.3.
I currently have two ideas for this: the first is simple, but definitely very slow, which goes through the whole array and finds where the array [i-1] is less than 2.1 and the array [i] is greater than 2.1.
Another way: add 2.1 to the array, sort the array in ascending order, the answer is index 2.1, and this index is 1.
Any other best suggestions?

Answer 1

You will 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);

Run codeHide result

Above code:

• It is assumed that the elements of the array are different and sorted in ascending order.
• Returns a pair of indices [i, i+1]
• Returns a pair of indices such that array[i] <= el < array[i+1]
• If the specified value is outside the range of the array, the output will be [-1, 0]if it is less than the first value of the array, or [n-1, n]when it is greater than the last value of the array ( narray length).
• Has a time complexity of O (log (n)).

Answer 2

This can be achieved using an algorithm binary insert.

Complexity:

best O (1), O (N). binary insert O(log(N)), O(N) , O(N) , - (N) .

, O(N) , 4 : let array=[3,6,9,10,20,21,23,24,26]

O(log(N)) O(N).

:

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);

Hide result

Answer 3

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));