搜索算法3：C ++语言的跳转搜索说明和实现

跳转搜索是对线性搜索的改进。在线性搜索中，我们逐一检查元素，直到找到关键元素，或者直到到达数组的末尾。

但是，如果我们能比线性搜索更快地找到关键元素呢？

答案就是跳转搜索。如果对数组排序，则跳转搜索将起作用。

在跳转搜索中，我们逐块跳转并检查关键元素是否在块内。如果键元素在该块内，则在该块中进行线性搜索。

如何选择块或跳转大小？

如果跳转大小为1，则将是线性搜索。因此，我们通常采用SQRT（n）的跳跃大小。这样，在最坏的情况下，我们会进行n / k个跳跃。

现在让我们借助示例来了解算法：

1，1，2，3，4，10，15，20，75，80，92，95，100

键= 80

N = 13

跳跃= SQRT（13）= 3

下图显示了通行证：

在C ++中跳转搜索

#include<iostream>
#include <cmath>
#include <vector>

using namespace std;

void jump_search(int arr[], int key, int len)
{

	int jump = sqrt(len);
	int start = 0;
	int end = start + jump;

	// get the correct block to search
    while (end < len && arr[end] <= key)
    {
    	// update the variables to make the jump.
   		start = end; 
      	end += jump;

      	// check if the end is greater than the size, 
      	//if 是, reset it.
      	if(end > len - 1)
       		end = len; 
    }

    // now do a linear search in the block
    for(int i = start; i<end; i++) 
    { 
      if(arr[i] == key)
       	cout<<" The key is present in the array"<<endl;
     	return;
   }
    cout<<" The key is NOT in the array"<<endl;
}


int main()
{
	int arr[20] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
	int key = 13;
	int len = 15;

	jump_search(arr, key, len);

	return 0;
}

进一步阅读：

AJ关于DS和算法的权威指南。单击此处以学习算法和数据结构教程的完整列表。 85多个章节可供学习。

该网站上可用的教程列表：