Jump Search Algorithm

The Jump Search Algorithm is an efficient search technique used to find a target value within a sorted array. It is an optimization over linear search, where you iterate through every element of the array one by one until the target value is found. Instead of checking every element, the Jump Search Algorithm "jumps" ahead by a specified block size, reducing the number of comparisons required to find the target value. If the value at the jump position is greater than the target value, the algorithm goes back to the previous block and performs a linear search within that block to find the exact position of the target value. The optimal block size is usually the square root of the array length, which minimizes the time complexity of the search algorithm. The Jump Search Algorithm is particularly useful for larger data sets, as it can significantly reduce the number of comparisons required to find the target value. The time complexity of the Jump Search Algorithm is O(√n), where n is the number of elements in the array, making it faster than linear search (O(n)) but slower than binary search (O(log n)). One key advantage of jump search over binary search is that it can work with data structures that do not support random access, such as linked lists, by simply jumping forward by a certain number of nodes. However, it is worth noting that the Jump Search Algorithm requires the input array to be sorted, as it relies on the order of elements to make informed jumps and comparisons.
package Search

/**
  * An implementation of the jump search algorithm in scala used
  * to search a sorted list
  */

import scala.math.{min, sqrt, floor}

object JumpSearch {

  /**
    * @param arr - a list of integers
    * @param elem - an integer to search for in @arr
    * @return - index of the @elem otherwise -1
    */

  def jumpSearch(arr: List[Int], elem: Int): Int = {

    val len = arr.size
    var a: Int = 0
    var b: Int = floor(sqrt(len)).toInt

    while (arr(min(b, len) - 1) < elem) {
      a = b
      b = b + floor(sqrt(len)).toInt
      if (a >= len){
        return -1
      }
    }

    while (arr(a) < elem) {
      a = a + 1
      if (a == min(b, len)) {
        return -1
      }
    }

    if (arr(a) == elem) {
      return a
    }
    else {
      return -1
    }
  }

}

LANGUAGE:

DARK MODE: