CODEWITHSUNDEEP
javascriptbinary-search
user2503048
user2503048

Reputation: 1041

JavaScript: quickly search for interval in array

A sorted array of numbers is given.

The idea is that for any given number, the code needs to find the two enclosing indices in the array such that:

array[a] <= query <= array[b]

For example, if the given array is [1, 20, 56, 200] and the number is 67, then 56 <= 67 <= 200 so the result is [2, 3].

I did a small test with a simple O(n) loop and two variants of a binary search, and surprisingly the loop was much faster for a low n (~0-100?). The test can be accessed here: http://jsperf.com/array-search-test/5

Is there a way to get something more optimized than those binary searches? this function runs thousands and tens of thousands times per second.

Upvotes: 0

Views: 373

Answers (2)

Bergi
Bergi

Reputation: 664764

I did a small test with a simple O(n) loop and two variants of a binary search, and surprisingly the loop was much faster for a low n (~0-100?). The test can be accessed here: http://jsperf.com/array-search-test/2

Sure, binary search has a large overhead compared to the much smaller loop body of the straightforward iteration.

What the big O notation describes "the limiting behavior [upper bound] of a function when the argument tends towards a particular value or infinity" and does not provide any evidence to compare two runs of particular implementations.

However, as @minitech noticed, your test case is flawed, and even at n=50 the binary search is already faster than the linear one. Here's an updated example, which also tests n=5 (where linear search is indeed faster) and nicely depicts the expected O(n) vs O(log N) difference in the graphs (though with exponential growth of the test data (5*10n) the graphs are exponential vs linear).

Is there a way to get something more optimized than those binary searches?

You might have a look at interpolation search.

this function runs thousands and tens of thousands times per second.

Why that? You might even better build a lookup table of your values then.

Upvotes: 1

Ry-
Ry-

Reputation: 225005

I did a small test with a simple O(n) loop and two variants of a binary search, and surprisingly the loop was much faster for a low n (~0-100?). The test can be accessed here: http://jsperf.com/array-search-test/2

First off, that’s how big-O works. In your binary search, there are many operations; sequential array access is relatively few.

But that’s not entirely what’s happening here. Your benchmarks don’t do what they claim.

In the benchmark labelled “O(n), n=50”, for example, n is still worst-case-1000. You’re just running 50 searches. However, since the tenth element of the array is 50, it’ll only ever do 50 comparisons. This isn’t true of the following binary searches; they both start at element 500. Hardly fair!

Make a few arrays.

Upvotes: 1

Related Questions