package Searches;

public class JumpSearch implements SearchAlgorithm {

  public static void main(String[] args) {
    JumpSearch jumpSearch = new JumpSearch();
    Integer[] array = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
    for (int i = 0; i < array.length; i++) {
      assert jumpSearch.find(array, i) == i;
    }
    assert jumpSearch.find(array, -1) == -1;
    assert jumpSearch.find(array, 11) == -1;
  }

  /**
   * Jump Search algorithm implements
   *
   * @param array the array contains elements
   * @param key to be searched
   * @return index of {@code key} if found, otherwise <tt>-1</tt>
   */
  @Override
  public <T extends Comparable<T>> int find(T[] array, T key) {
    int length = array.length; /* length of array */
    int blockSize = (int) Math.sqrt(length); /* block size to be jumped */

    int limit = blockSize;
    while (key.compareTo(array[limit]) > 0 && limit < array.length - 1) {
      limit = Math.min(limit + blockSize, array.length - 1);
    }

    for (int i = limit - blockSize; i <= limit; i++) {
      if (array[i] == key) {
        /* execute linear search */
        return i;
      }
    }
    return -1; /* not found */
  }
}