跳转查找 Jump search

图解

使用已排序数组是这个算法的先前条件。从左边开始每次跳过一定的长度，如果发现搜寻的数字在上一个跳过的数据里再往回用线性搜索。

造轮子！！

public int jumpSearch(int[] arr, int x) 
   { 
       int n = arr.length; 
 
       // Finding block size to be jumped 
       int step = (int)Math.floor(Math.sqrt(n)); 
 
       // Finding the block where element is 
       // present (if it is present) 
       int prev = 0; 
       while (arr[Math.min(step, n)-1] < x) 
       { 
           prev = step; 
           step += (int)Math.floor(Math.sqrt(n)); 
           if (prev >= n) 
               return -1; 
       } 
 
       // Doing a linear search for x in block 
       // beginning with prev. 
       while (arr[prev] < x) 
       { 
           prev++; 
 
           // If we reached next block or end of 
           // array, element is not present. 
           if (prev == Math.min(step, n)) 
               return -1; 
       } 
 
       // If element is found 
       if (arr[prev] == x) 
           return prev; 
 
       return -1; 
   } 

复杂度分析

时间：
	假设每次跳跃m

	最坏情况：跳n/m次，然后再往回查询m-1
		k = n/m + m - 1

	最差复杂性： O(sqrt(n))


空间：
	复杂性： O(1)

未完
类似方法 指数搜索 (Exponential Search)
其它
Fibonacci Search
The Ubiquitous Binary Search