Jump Search
Jump Search is another searching algorithm that can be used on sorted collections (arrays or lists). The idea is to reduce the number of comparisons by jumping ahead by fixed steps or skipping some elements in place of searching all elements.
Illustration of Jump Search:
Let’s consider the following array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610).
The length of the array is 16. The Jump search will find the value of 55 with the following steps assuming that the block size to be jumped is 4.
- Jump from index 0 to index 4;
- Jump from index 4 to index 8;
- Jump from index 8 to index 12;
- Since the element at index 12 is greater than 55, we will jump back a step to come to index 8.
- Perform a linear search from index 8 to get the element 55.
Time Complexity of Jump Search:
- Time Complexity: O(√n), where “n” is the number of elements in the collection. This makes it more efficient than Linear Search but generally less efficient than Binary Search for large datasets.
- Auxiliary Space: O(1), as it uses a constant amount of additional space for variables.
Performance Comparison based on Complexity:
linear search < jump search < binary search
Introduction to Searching – Data Structure and Algorithm Tutorial
Searching is the fundamental process of locating a specific element or item within a collection of data. This collection of data can take various forms, such as arrays, lists, trees, or other structured representations.
The primary objective of searching is to determine whether the desired element exists within the data, and if so, to identify its precise location or retrieve it. It plays an important role in various computational tasks and real-world applications, including information retrieval, data analysis, decision-making processes, and more.