Find what all amongst a bunch of integers exist in a sorted array

Question

Possible Duplicate:
Simplest code for array intersection in javascript

I have a sorted array of integers in javascript. I need to find out which all amongst a bunch of integers exists in that sorted array. What would be the fastest way to do that?

I use jQuery, but it seems that it provides no built in support for binary search for sorted arrays but just jQuery.inArray()(not sure what algo it implements).

Loop, just loop: https://github.com/jquery/jquery/blob/master/src/core.js#L660. — VisioN, Dec 05 '12 at 14:39
`jQuery.inArray()` attempts to use `Array.indexOf` and if not, uses its own implementation of it. All you need to do is loop through the bunch of integers and check if `your_array.indexOf(item) > -1`, meaning it is in the array. — Ian, Dec 05 '12 at 14:39
Is the *bunch of integers* in an array ? Do you want the intersection of two arrays of integers ? — Gabriele Petrioli, Dec 05 '12 at 14:39
@Gaby aka G. Petrioli: the bunch of integers are not in array, I just iterate through some dom elements for them — Rajat Gupta, Dec 05 '12 at 14:48
Ok, then you might want to add this to the question and also explain how you iterate over the DOM elements.. show us what you currently have, what you want to get, and what you have tried.. — Gabriele Petrioli, Dec 05 '12 at 14:50
isn't there any specialized search method for sorted arrays ? — Rajat Gupta, Dec 05 '12 at 14:50
for single items yes.. `arrayvariable.indexOf(value)` will return the position it found the `value` in the `arrayvarialble` or -1 if not found.. — Gabriele Petrioli, Dec 05 '12 at 14:58
but I guess indexOf(value) would also tell index by iterating throughout array & finding position of matched element !? No? — Rajat Gupta, Dec 05 '12 at 15:03
You may want to see my [Array Set Math](http://phrogz.net/JS/ArraySetMath.js) library, which provides the ability to find the intersection of two sorted arrays (which would shown you the elements in common to them both). — Phrogz, Dec 05 '12 at 15:13

Julien Royer · Answer 1 · 2012-12-05T15:08:27.500

Neither the JavaScript language nor jQuery provide a binary search function.

It would look like this:

function binarySearch(array, val, cmp) {
  cmp = cmp || function(v1, v2) { return v1 - v2; };
  var l = 0, h = array.length - 1;
  while (l <= h) {
    var m = Math.round((l + h) / 2), diff = cmp(array[m], val);
    if (!diff) {
      return m;
    }
    diff > 0 ? (h = m - 1) : (l = m + 1);
  }

  return -1;
}

binarySearch([1, 10, 100, 1000], 666); // -1

Find what all amongst a bunch of integers exist in a sorted array

1 Answers1