数据结构和算法

DSA - 主页 DSA - 概述 DSA - 环境设置 DSA - 算法基础 DSA - 渐近分析

数据结构

DSA - 数据结构基础 DSA - 数据结构和类型 DSA - 数组数据结构

链接列表

DSA - 链接列表数据结构 DSA - 双向链接列表数据结构 DSA - 循环链表数据结构

堆栈 &队列

DSA - 堆栈数据结构 DSA - 表达式解析 DSA - 队列数据结构

搜索算法

DSA - 搜索算法 DSA - 线性搜索算法 DSA - 二分搜索算法 DSA - 插值搜索 DSA - 跳跃搜索算法 DSA - 指数搜索 DSA - 斐波那契搜索 DSA - 子列表搜索 DSA - 哈希表

排序算法

DSA - 排序算法 DSA - 冒泡排序算法 DSA - 插入排序算法 DSA - 选择排序算法 DSA - 归并排序算法 DSA - 希尔排序算法 DSA - 堆排序 DSA - 桶排序算法 DSA - 计数排序算法 DSA - 基数排序算法 DSA - 快速排序算法

图形数据结构

DSA - 图形数据结构 DSA - 深度优先遍历 DSA - 广度优先遍历 DSA - 生成树

树数据结构

DSA - 树数据结构 DSA - 树遍历 DSA - 二叉搜索树 DSA - AVL 树 DSA - 红黑树 DSA - B树 DSA - B+ 树 DSA - 伸展树 DSA - 尝试 DSA - 堆数据结构

递归

DSA - 递归算法 DSA - 使用递归的汉诺塔 DSA - 使用递归的斐波那契数列

分而治之

DSA - 分而治之 DSA - 最大最小问题 DSA - 施特拉森矩阵乘法 DSA - Karatsuba 算法

贪婪算法

DSA - 贪婪算法 DSA - 旅行商问题(贪婪方法) DSA - Prim 最小生成树 DSA - Kruskal 最小生成树 DSA - Dijkstra 最短路径算法 DSA - 地图着色算法 DSA - 分数背包问题 DSA - 作业排序截止日期 DSA - 最佳合并模式算法

动态规划

DSA - 动态规划 DSA - 矩阵链乘法 DSA - Floyd Warshall 算法 DSA - 0-1 背包问题 DSA - 最长公共子序列算法 DSA - 旅行商问题(动态方法)

近似算法

DSA - 近似算法 DSA - 顶点覆盖算法 DSA - 集合覆盖问题 DSA - 旅行商问题(近似方法)

随机算法

DSA - 随机算法 DSA - 随机快速排序算法 DSA - Karger 最小割算法 DSA - Fisher-Yates 洗牌算法

DSA 有用资源

DSA - 问答 DSA - 快速指南 DSA - 有用资源 DSA - 讨论


Jump Search Algorithm



Jump Search algorithm is a slightly modified version of the linear search algorithm. The main idea behind this algorithm is to reduce the time complexity by comparing lesser elements than the linear search algorithm. The input array is hence sorted and divided into blocks to perform searching while jumping through these blocks.

For example, let us look at the given example below; the sorted input array is searched in the blocks of 3 elements each. The desired key is found only after 2 comparisons rather than the 6 comparisons of the linear search.

Jump_Search

Here, there arises a question about how to divide these blocks. To answer that, if the input array is of size ‘n’, the blocks are divided in the intervals of √n. First element of every block is compared with the key element until the key element’s value is less than the block element. Linear search is performed only on that previous block since the input is sorted. If the element is found, it is a successful search; otherwise, an unsuccessful search is returned.

Jump search algorithm is discussed in detail further into this chapter.

Jump Search Algorithm

The jump search algorithm takes a sorted array as an input which is divided into smaller blocks to make the search simpler. The algorithm is as follows −

Step 1 − If the size of the input array is ‘n’, then the size of the block is √n. Set i = 0.

Step 2 − The key to be searched is compared with the ith element of the array. If it is a match, the position of the element is returned; otherwise i is incremented with the block size.

Step 3 − The Step 2 is repeated until the ith element is greater than the key element.

Step 4 − Now, the element is figured to be in the previous block, since the input array is sorted. Therefore, linear search is applied on that block to find the element.

Step 5 − If the element is found, the position is returned. If the element is not found, unsuccessful search is prompted.

Pseudocode

Begin
   blockSize := √size
   start := 0
   end := blockSize
   while array[end] <= key AND end < size do
      start := end
      end := end + blockSize
      if end > size – 1 then
         end := size
   done
   for i := start to end -1 do
      if array[i] = key then
         return i
   done
   return invalid location
End

Analysis

The time complexity of the jump search technique is O(√n) and space complexity is O(1).

Example

Let us understand the jump search algorithm by searching for element 66 from the given sorted array, A, below −

jump_search_algorithm

Step 1

Initialize i = 0, and size of the input array ‘n’ = 12

Suppose, block size is represented as ‘m’. Then, m = √n = √12 = 3

Step 2

Compare A[0] with the key element and check whether it matches,

A[0] = 0 ≠ 66

Therefore, i is incremented by the block size = 3. Now the element compared with the key element is A[3].

compare_index_3

Step 3

A[3] = 14 ≠ 66

Since it is not a match, i is again incremented by 3.

incremented_3

Step 4

A[6] = 48 ≠ 66

i is incremented by 3 again. A[9] is compared with the key element.

compare_with_index_6

Step 5

A[9] = 88 ≠ 66

However, 88 is greater than 66, therefore linear search is applied on the current block.

88_greater_than_66

Step 6

After applying linear search, the pointer increments from 6th index to 7th. Therefore, A[7] is compared with the key element.

returns_7th_index

We find that A[7] is the required element, hence the program returns 7th index as the output.

Implementation

The jump search algorithm is an extended variant of linear search. The algorithm divides the input array into multiple small blocks and performs the linear search on a single block that is assumed to contain the element. If the element is not found in the assumed blocked, it returns an unsuccessful search.

The output prints the position of the element in the array instead of its index. Indexing refers to the index numbers of the array that start from 0 while position is the place where the element is stored.

#include<stdio.h>
#include<math.h>
int jump_search(int[], int, int);
int main(){
   int i, n, key, index;
   int arr[12] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
   int len = sizeof(arr)/sizeof(arr[0]);
   printf("Array elements are:");
   for(int j = 0; j<len; j++){
      printf(" %d", arr[j]);
   }
   n = 12;
   key = 66;
   printf("
The element to be searched: %d
", key);
   index = jump_search(arr, n, key);
   if(index >= 0)
      printf("The element is found at position %d", index+1);
   else
      printf("Unsuccessful Search");
   return 0;
}
int jump_search(int arr[], int n, int key){
   int i, j, m, k;
   i = 0;
   m = sqrt(n);
   k = m;
   while(arr[m] <= key && m < n) {
      i = m;
      m += k;
      if(m > n - 1)
         return -1;
   }

   // linear search on the block
   for(j = i; j<m; j++) {
      if(arr[j] == key)
         return j;
   }
   return -1;
}

Output

Array elements are: 0 6 12 14 19 22 48 66 79 88 104 126
The element to be searched: 66
The element is found at position 8
#include<iostream>
#include<cmath>
using namespace std;
int jump_search(int[], int, int);
int main(){
   int i, n, key, index;
   int arr[12] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
   printf("Array elements are: ");
   for (auto j : arr){
      cout<<j<<" ";
   }
   n = 12;
   key = 66;
    cout<<"
The element to be searched: "<<key<<endl;
   index = jump_search(arr, n, key);
   if(index >= 0)
      cout << "The element is found at position " << index+1;
   else
      cout << "Unsuccessful Search";
   return 0;
}
int jump_search(int arr[], int n, int key){
   int i, j, m, k;
   i = 0;
   m = sqrt(n);
   k = m;
   while(arr[m] <= key && m < n) {
      i = m;
      m += k;
      if(m > n - 1)
         return -1;
   }

   // linear search on the block
   for(j = i; j<m; j++) {
      if(arr[j] == key)
         return j;
   }
   return -1;
}

Output

Array elements are: 0 6 12 14 19 22 48 66 79 88 104 126 
The element to be searched: 66
The element is found at position 8
import java.io.*;
import java.util.Scanner;
import java.lang.Math;
public class JumpSearch {
   public static void main(String args[]) {
      int i, n, key, index;
      int arr[] = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
	  System.out.println("Array elements are: ");
	  for(int j = 0; j<arr.length; j++){
	     System.out.print(arr[j] + " ");
	  }
      n = 12;
      key = 66;
	  System.out.println("
The element to be searched: "+ key);
      index = jump_search(arr, n, key);
      if(index >= 0)
         System.out.print("The element is found at position " + (index+1));
      else
         System.out.print("Unsuccessful Search");
   }
   static int jump_search(int arr[], int n, int key) {
      int i, j, m, k;
      i = 0;
      m = (int)Math.sqrt(n);
      k = m;
      while(arr[m] <= key && m < n) {
         i = m;
         m += k;
         if(m > n - 1)
            return -1;
      }
      
      // linear search on the block
      for(j = i; j<m; j++) {
         if(arr[j] == key)
            return j;
      }
      return -1;
   }
}

Output

Array elements are: 
0 6 12 14 19 22 48 66 79 88 104 126 
The element to be searched: 66
The element is found at position 8
import math
def jump_search(a, n, key):
   i = 0
   m = int(math.sqrt(n))
   k = m
   while(a[m] <= key and m < n):
      i = m
      m += k
      if(m > n - 1):
         return -1
   for j in range(m):
      if(arr[j] == key):
         return j
   return -1

arr = [0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126]
n = len(arr);
print("Array elements are: ")
for i in range(n):
   print(arr[i], end = " ")
key = 66
print("
The element to be searched: ", key)
index = jump_search(arr, n, key)
if(index >= 0):
   print("The element is found at position: ", (index+1))
else:
   print("
Unsuccessful Search")

Output

Array elements are: 
0 6 12 14 19 22 48 66 79 88 104 126 
The element to be searched:  66
The element is found at position:  8