More general binary search in JS

What is binary search?

We're all pretty familiar with basic binary search - given a sorted array, provide an element. If it exists, return its index, if not, -1.

Its better than just walking through the array since it leverages the fact that the array is sorted by splitting up the search into halves, thereby providing a O(log n) runtime complexity instead of O(n).

You might find that a typical binary search algorithm looks something like this:

function binarySearch(list, value) {
  // start, middle, end
  let start = 0;
  let end = list.length - 1;
  let mid = Math.floor((start + end) / 2);

  // While the middle is not what we're looking for and the list does not have single item
  while (list[mid] !== value && start < end) {
  	// modify search window
    if (value < list[mid]) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }

    // new mid value
    mid = Math.floor((start + end) / 2);
  }

  // at the end, either mid is where the value is, or not
  return value !== list[mid] ? -1 : mid;
}

This works well for arrays of primitives, say something like

# Example 1:

binarySearch([1, 2, 3, 4], 1); // => 0

Some problems with this approach

But what if instead you did something like,

# Example 2:

binarySearch([[1,2],[2,3],[3,4]], [1,2]); //=> -1

or even,

# Example 3:

function someObject(start, end) {
  this.start = start;
    this.end = end;
};

const A = new someObject(1, 2);
const B = new someObject(3, 4);
const C = new someObject(1, 2);

binarySearch([A, B], C); // => -1

Digging into the details

In both cases above, the algorithm fails to identify a suitable match for the value passed in. In principle, we are attempting to apply the same logic; the reason it fails, is the nature of the comparison steps in the algorithm,

list[mid] !== value

value < list[mid]

For more complex objects, equality comparisons might not be as straight forward as simple strict equality checking with ===, and comparison with <. For instance, in example 3, the object A and C had the same constituent properties. Perhaps, we would want those to be considered equal. Simply doing something like list[mid] !== value however, would not suffice, since they are technically "different" objects.

Similarly, in example 2, there is really no meaning to something like [1, 2] !== [1, 2] or [1, 2] < [1, 2].

What can be said in each case however, is that if the individual components of the objects were compared somehow, it is possible to better perform equality and comparison checks.

The solution?

We would however want a more general way to allow this - of course, still assuming arrays of homogenous objects. Enter functions! Instead of providing only a single way to do comparisons and equality checks, we will allow the user to define how they'd like to do it, based on the nature of their data.

We really only need 3

• equality function
• comparison function (for less than check)
• accessor function (in case we are searching over something that is more complex than a traditional array)

function binarySearch(list, value,
  valueLt = (cmp, value) => cmp > value,
  valueEq = (cmp, value) => cmp === value,
  accessor = (list, idx) => list[idx]
) {
  // start, middle, end
  let start = 0;
  let end = list.length - 1;
  let mid = Math.floor((start + end) / 2);

  // While the middle is not what we're looking for and the list does not have a single item
  while (!valueEq(accessor(list, mid), value) && start < end) {
  	// modify search window
    if (valueLt(accessor(list, mid), value)) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }

    // new mid value
    mid = Math.floor((start + end) / 2);
  }

  // at the end, either mid is where the value is, or not
  return !valueEq(accessor(list, mid), value) ? -1 : mid;
}

Note how we default to the original binary search algorithm if nothing is passed in for those functions, so that we retain basic binary search.

# Example 4: Example 2 revisited

const valueLt = (cmp, value) => {
  return cmp && cmp[0] > value[0] && cmp[1] > value[1];
};

const valueEq = (cmp, value) => {
  return cmp && cmp[0] === value[0] && cmp[1] === value[1];
};

list = [[1,2], [2,3], [3,4]];
binarySearch(list, [1,2], valueLt, valueEq); // => 0

# Example 5: Example 3 revisited

function someObject(start, end) {
  this.start = start;
    this.end = end;
};

const A = new someObject(1, 2);
const B = new someObject(3, 4);
const C = new someObject(1, 2);

const valueLt = (cmp, value) => {
  return cmp && cmp.start > value.start && cmp.end > value.end;
};

const valueEq = (cmp, value) => {
  return cmp && cmp.start === value.start && cmp.end === value.end;
};

binarySearch([A, B], C, valueLt, valueEq); // => 0

As we can see, we are able to define custom comparison and equality functions that allow us to handle different types of objects, while using the same algorithm.

Thanks for reading!