Jump Search using Java....

Jump Search - Jump Search is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements.

Input - A sorted array.

Here is the code .....

       
public class JumpSearch {

 public static void main(String[] args) {

  int[] arr = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610 };
  int lastJumpedIndex = 0;

  // Evaluate optimal block size
  int t = (int) Math.floor(Math.sqrt(arr.length));
  int valueToSearch = 21;

  while (t < arr.length) {

   if (arr[t] > valueToSearch) {

    if (valueToSearch >= arr[lastJumpedIndex]) {

     // Doing a linear search for x in block
     int i = lastJumpedIndex;
     while (i < t) {
      if (arr[i] == valueToSearch) {
       System.out.print("Element found at index : " + i);
       return;
      }
      i++;
     }
    }
   }
   lastJumpedIndex = t;
   t = 2 * t;
  }

  // In case few of the elements in the last iteration of above loop have
  // left if array is not of an even length
  if (t > arr.length - 1) {
   int k = lastJumpedIndex;
   while (k <= arr.length - 1) {
    if (arr[k] == valueToSearch) {
     System.out.print("Element found at index : " + k);
     return;
    }
    k++;
   }
  }
  System.out.print("Element was not found");
 }

 public static int min(int i, int j) {
  if (i < j)
   return i;
  else
   return j;
 }
}