JavaScript Jump Search

Posted on: 2017-06-20

The Jump Search algorithm allows to combine a linear search with a speed optimization. This mean that instead of going 1 by 1, we will increase the step of √n and increase that step of √n which make the step getting bigger and bigger.

The asymptotic analysis of Jump Search is o(√n). Like the binary search, it needs to be sorted. The advantage against binary search is that Jump Search traversed back only once.

var arrayToSearch = [2, 6, 8, 12, 43, 78, 99, 134, 144, 156, 199, 256, 500];

console.log("Found at position :" + jumpSearch(arrayToSearch, 2));
console.log("Found at position :" + jumpSearch(arrayToSearch, 256));
console.log("Found at position :" + jumpSearch(arrayToSearch, 500));
console.log("Found at position :" + jumpSearch(arrayToSearch, 44444));

function jumpSearch(arrayToSearch, valueToSearch) {
  var length = arrayToSearch.length;
  var step = Math.floor(Math.sqrt(length));
  var index = Math.min(step, length) - 1;
  var lowerBound = 0;
  while (arrayToSearch[Math.min(step, length) - 1] < valueToSearch) {
    lowerBound = step;
    step += step;
    if (lowerBound >= length) {
      return -1;
    }
  }
  var upperBound = Math.min(step, length);
  while (arrayToSearch[lowerBound] < valueToSearch) {
    lowerBound++;
    if (lowerBound == upperBound) {
      return -1;
    }
  }
  if (arrayToSearch[lowerBound] == valueToSearch) {
    return lowerBound;
  }
  return -1;
}

It requires two loops. The first loop looks at value to determine if the value is under or not the jump. This one will set the lower bound variable that contains the lower bound of the linear search. The second loop does the linear from the lower bound to the upper bound. The upper bound can be the end of the array, or if a step.