CODEWITHSUNDEEP
javascriptarraysalgorithm
MaXon
MaXon

Reputation: 475

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

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?

Upvotes: 6

Views: 2804

Answers (3)

trincot
trincot

Reputation: 350345

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.

Upvotes: 2

Mihai Alexandru-Ionut
Mihai Alexandru-Ionut

Reputation: 48367

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: enter image description here

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

Upvotes: 0

Ramesh Lamba
Ramesh Lamba

Reputation: 61

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

Upvotes: 0

Related Questions