Jump Search

public class JumpSearch {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		
		int arr[] = {0,1,21,32,44,56,61,76,83,94,101};
		
		int elementToSearch = 44;
		
		System.out.println("Searching for the element ::"+elementToSearch);
		
		int index = jumpSearch(arr,elementToSearch);
		
		
		System.out.println("Element found at index ::"+index);
	}

	public static int jumpSearch(int arr[], int elementToSearch){
		int index = -1;
		
		//finding the block size
		int blockSize = (int)Math.floor(Math.sqrt(arr.length));
		
		//finding the block where elementToSeach may be present;
		int blockStart = 0;
		while(arr[Math.min(blockSize, arr.length)-1] arr.length-1)
				return -1;
		}
		
		while(arr[blockStart] Math.min(blockSize, arr.length))
				return -1;
			
			if(arr[blockStart]==elementToSearch)
				return blockStart;
			
			
			blockStart++;
		}
		return index;
	}
	
}

Output :

Searching for the element ::44
Element found at index ::4