JavaScript Exponential Search

Posted on: 2017-06-26

An exponential search is a search the binary search with a little difference that it will try to not have to divide in two the whole array but just a subset. This subset is decided by jumping in the array in an exponential way. At some point, the value found will be bigger than the one searched which is where we stop jumping and applying the binary search.

The first step is to bring the binary search:

function binarySearch(arrayToSearch, valueToSearch, start, end) {
  if (start <= end) {
    var middle = Math.ceil((end + start) / 2);
    var middleValue = arrayToSearch[middle];
    if (middleValue === valueToSearch) {
      return middle;
    } else if (valueToSearch < middleValue) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    return binarySearch(arrayToSearch, valueToSearch, start, end);
  }
  return -1;
}

The exponential search come right before:

function exponentialSearch(arrayToSearch, valueToSearch, length) {
  if (arrayToSearch[0] == valueToSearch) {
    return 0;
  }

  var i = 1;
  while (i < length && arrayToSearch[i] <= valueToSearch) {
    i = i * 2;
  }
  return binarySearch(
    arrayToSearch,
    valueToSearch,
    i / 2,
    Math.min(i, length - 1)
  );
}

Even with this optimization, the search still at O(log n). As we can see on the last line, we call the binary search by not starting with zero, but with the value found with the exponential while.