Back to Course

Algorithm

0% Complete
0/82 Steps
  1. Getting Started with Algorithm
    What is an Algorithm?
  2. Characteristics of Algorithm
    1 Topic
  3. Analysis Framework
  4. Performance Analysis
    3 Topics
  5. Mathematical Analysis
    2 Topics
  6. Sorting Algorithm
    Sorting Algorithm
    10 Topics
  7. Searching Algorithm
    6 Topics
  8. Fundamental of Data Structures
    Stacks
  9. Queues
  10. Graphs
  11. Trees
  12. Sets
  13. Dictionaries
  14. Divide and Conquer
    General Method
  15. Binary Search
  16. Recurrence Equation for Divide and Conquer
  17. Finding the Maximum and Minimum
  18. Merge Sort
  19. Quick Sort
  20. Stassen’s Matrix Multiplication
  21. Advantages and Disadvantages of Divide and Conquer
  22. Decrease and Conquer
    Insertion Sort
  23. Topological Sort
  24. Greedy Method
    General Method
  25. Coin Change Problem
  26. Knapsack Problem
  27. Job Sequencing with Deadlines
  28. Minimum Cost Spanning Trees
    2 Topics
  29. Single Source Shortest Paths
    1 Topic
  30. Optimal Tree Problem
    1 Topic
  31. Transform and Conquer Approach
    1 Topic
  32. Dynamic Programming
    General Method with Examples
  33. Multistage Graphs
  34. Transitive Closure
    1 Topic
  35. All Pairs Shortest Paths
    6 Topics
  36. Backtracking
    General Method
  37. N-Queens Problem
  38. Sum of Subsets problem
  39. Graph Coloring
  40. Hamiltonian Cycles
  41. Branch and Bound
    2 Topics
  42. 0/1 Knapsack problem
    2 Topics
  43. NP-Complete and NP-Hard Problems
    1 Topic
Lesson 7, Topic 6
In Progress

Jump Search

Lesson Progress
0% Complete

Jump search technique also works for ordered lists. It creates a block and tries to find the element in that block. If the item is not in the block, it shifts the entire block. The block size is based on the size of the list. If the size of the list is n then block size will be √n. After finding a correct block it finds the item using a linear search technique. The jump search lies between linear search and binary search according to its performance.

Lets consider a sorted array A[] of size n, with indexing ranging between 0 and n-1, and element x that needs to be searched in the array A[]. For implementing this algorithm, a block of size m is also required, that can be skipped or jumped in every iteration. Thus, the algorithm works as follows:

  • Iteration 1: if (x==A[0]), then success, else, if (x > A[0]), then jump to the next block.
  • Iteration 2: if (x==A[m]), then success, else, if (x > A[m]), then jump to the next block.
  • Iteration 3: if (x==A[2m]), then success, else, if (x > A[2m]), then jump to the next block.
  • At any point in time, if (x < A[km]), then a linear search is performed from index A[(k-1)m] to A[km]

What is the optimal block size to be skipped?
In the worst case, we have to do n/m jumps and if the last checked value is greater than the element to be searched for, we perform m-1 comparisons more for linear search. Therefore the total number of comparisons in the worst case will be ((n/m) + m-1). The value of the function ((n/m) + m-1) will be minimum when m = √n. Therefore, the best step size is m = √n.

Jump search algorithm, also called as block search algorithm. Only sorted list of array or table can alone use the Jump search algorithm. In jump search algorithm, it is not at all necessary to scan every element in the list as we do in linear search algorithm. We just check the R element and if it is less than the key element, then we move to the R + R element, where all the elements between R element and R + R element are skipped. This process is continued until R element becomes equal to or greater than key element called boundary value. The value of R is given by R = sqrt(n), where n is the total number of elements in an array. Once the R element attain the boundary value, a linear search is done to find the key value and its position in the array. It must be noted that in Jump search algorithm, a linear search is done in reverse manner that is from boundary value to previous value of R.

Steps for Jump Search Algorithms:

Step 1: Set i=0 and m = √n.

Step 2: Compare A[i] with item. If A[i] != item and A[i] < item, then jump to the next block. Also, do the following:

  1. Set i = m
  2. Increment m by √n

Step 3: Repeat the step 2 till m < n-1

Step 4: If A[i] > item, then move to the beginning of the current block and perform a linear search.

  1. Set x = i
  2. Compare A[x] with item. If A[x]== item, then print x as the valid location else set x++
  3. Repeat Step 4.1 and 4.2 till x < m

Step 5: Exit

Let us trace the above algorithm using an example:

Consider the following inputs:

  • A[] = {0, 1, 1, 2, 3, 5, 8, 13, 21, 55, 77, 89, 101, 201, 256, 780}
  • item = 77

Step 1m = √n = 4 (Block Size)

Step 2: Compare A[0] with item. Since A[0] != item and A[0]<item, skip to the next block

Comparing a[0] operator

Figure 2: Comparing A[0] and item

Step 3: Compare A[3] with item. Since A[3] != item and A[3]<item, skip to the next block

comparing a[3] operator

Figure 3: Comparing A[3] and item

Step 4: Compare A[6] with item. Since A[6] != itemand A[6]<item, skip to the next block

comparing a[6] operator

Figure 4: Comparing A[6] and item

Step 5: Compare A[9] with item. Since A[9] != itemand A[9]<item, skip to the next block

Comparing a[9] operator

Figure 5: Comparing A[9] and item

Step 6: Compare A[12] with item. Since A[12] != item and A[12] >item, skip to A[9] (beginning of the current block) and perform a linear search.

comapring a[12] operator

Figure 6: Comparing A[12] and item

comparing-  a[12] -2

Figure 7: Comparing A[9] and item (Linear Search)

  • Compare A[9] with item. Since A[9] != item, scan the next element
  • Compare A[10] with item. Since A[10] == item, index 10 is printed as the valid location and the algorithm will terminate

comapring-a[10]

Figure 8: Comparing A[10] and item (Linear Search)

Example – Jump Search

In 16 elements of array, we need to find our key element 7 using jump search algorithm.

step 1: Find the value of R. here R = sqrt (16) i.e) R = 4.

step 2: Skip the first three elements(1, 2, 3) in the array and check whether fourth(4) value is equal to or greater than key value(7).

step 3: If not skip next three elements(5, 6, 7) in the array and check whether eighth(8) value is equal to or greater than key value(7). In this case it is greater than Key value.

step 4: Now by using linear search algorithm, move reverse from value 8(boundary value) to value 4(previous value) to find the key value(7).

step 5: Thus using linear search algorithm the Key value is calculated and resulted in position array[6].

The complexity of Jump Search Technique

  1. Time Complexity: O(√n)
  2. Space Complexity: O(1)

Input and Output

Input:
A sorted list of data:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
The search key 356
Output:
Item found at location: 11

Algorithm

jumpSearch(array, size, key)

Input: An sorted array, size of the array and the search key

Output: location of the key (if found), otherwise wrong location.

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

Jump Search Program in C

#include<iostream>
#include<cmath>

using namespace std;
int jumpSearch(int array[], int size, int key) {
   int start = 0;
   int end = sqrt(size); //the square root of array length

   while(array[end] <= key && end < size) {
      start = end; //it it is not correct block then shift block
      end += sqrt(size);
      if(end > size - 1)
         end = size; //if right exceeds then bound the range
   }

   for(int i = start; i<end; i++) { //perform linear search in selected block
      if(array[i] == key)
         return i; //the correct position of the key
   }
   return -1;
}

int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n]; //create an array of size n
   cout << "Enter items: " << endl;

   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }

   cout << "Enter search key to search in the list: ";
   cin >> searchKey;
   if((loc = jumpSearch(arr, n, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

Output :

Enter number of items: 20
Enter items:
10 13 15 26 28 50 56 88 94 127 159 356 480 567 689 699 780 850 956 995
Enter search key to search in the list: 356
Item found at location: 11

Advantages – Jump Search

  • Jump search algorithm is more efficient in case of finding a element 600 out of 625 elements in an array.
  • Jump search algorithm takes 25 iteration to find a element 600 out of 625 elements in an array.
  • Whereas Linear search algorithm takes 600 iteration to find a element 600 out of 625 elements in an array.
  • Whereas Binary search algorithm takes 19 iteration to find a element 600 out of 625 elements in an array but complexity in calculation is very tough as compared to jump search algorithm.

Disadvantages – Jump Search

  • Jump search algorithm is not preferable for unsorted list or array.
  • Executing time of Binary search algorithm is 0 (sqrt (n)).
KodNest Training New Batch is starting on 02nd November 2020. Attend one week free demo classes.Register Now

New Report

Close