Welcome back, brave explorers! In the first part of our series, we covered the fundamental searching algorithms, including Linear Search, Binary Search, and Hashing. If you missed it, be sure to check it out here. It’s time to level up our searching game with more advanced techniques. Get ready to discover the secrets of Jump Search, Interpolation Search, Exponential Search, and Ternary Search!
The Leaping Lizard — Jump Search
You are a lizard, jumping from lily pad to lily pad across a pond, but you’re looking for a specific lily pad. You don’t check each lily pad, but you do much larger jumps to travel more distance quicker. Well, that is Jump Search in a nutshell.
How does Jump Search work?
Jump Search, a method that efficiently locates an element in a sorted array, is a fascinating technique. It involves jumping ahead with a block size, which is calculated as the square root of the sorted array length. A linear search is performed within that block when an element greater than the target element is found. This method ensures the target element is found within the block if it exists in the array, making it a speedy and efficient search algorithm.
Algorithm
- Sort the array if it still needs to be sorted.
- Calculate block size to jump. Generally, it is the square root of the array length.
- Traverse the sorted array and jump elements based on the calculated block size.
- Perform a linear search when the current value exceeds the given value.
- Return the index of the element as soon as you find a match.
Jump Search Example
Let’s use an example to illustrate. Suppose you have the sorted elements 10, 20, 30, 40, 50, 60, 70, 80, 90 and want to search for 60.
- First, calculate the block size for jumping, which is √9 = 3. You will traverse this sorted array and skip 3 elements each time.
- At each step, compare the current element with the target element. If the current element is less than the target, jump to the next block. If the current element exceeds the target, perform a linear search from the previous block to the current one.
- In this example, start at index 0, then jump to index 3, and then to index 6. At index 6, you find the element 70, which is greater than 60. So, you start a linear search from index 3 to index 6. Return the index of the component as soon as you find a match.
Code Example
import java.lang.Math;
public class JumpSearch {
public static int jumpSearch(int[] arr, int target, int jumpSize) {
int arrLength = arr.length;
// Check if target element is present at the beginning
if (arr[0] == target) {
return 0;
}
int currArrPos = jumpSize;
// Find the block where the element might lie
while (currArrPos < arrLength && arr[currArrPos - 1] < target) {
currArrPos += jumpSize;
}
// If target element is within the current block
int right = Math.min(currArrPos, arrLength - 1);
// Linear search within the narrowed block
return linearSearch(arr, currArrPos - jumpSize, right, target);
}
// Helper function for linear search within a specific range
private static int linearSearch(int[] arr, int left, int right, int target) {
for (int i = left; i <= right; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}
public static void main(String[] args) {
int jumpSize, target, result;
int[] arr = {0, 6, 12, 14, 19, 22, 48, 66, 79, 88, 104, 126};
jumpSize = (int) Math.sqrt(arr.length);
target = 104;
result = jumpSearch(arr, target, jumpSize);
if (result >= 0)
System.out.print("The element is found at position " + (result));
else
System.out.print("Unsuccessful Search");
}
}
Pros
- Better than a linear search for large, uniformly distributed arrays
- It has a lower time complexity compared to a linear search for large arrays
Cons
- Requires sorting the data set beforehand, which adds extra cost.
- Less efficient than binary search
Complexity
- Time Complexity: O(√n)
- Space Complexity: O(1)
The Ternary Dilemma — Ternary Search
The Ternary Search algorithm, a straightforward divide-and-conquer search technique, finds an element in a sorted array. It is similar to binary search but divides the array into three parts instead of two. Then, one part is eliminated based on the comparison with the target value, repeating the process until the target is found or the search space is empty. This simplicity makes it a comfortable and reliable search algorithm to use in some cases.
Algorithm
Imagine you have a sorted list, like numbers from small to big. We can divide the list by taking two midpoints, mid1 and mid2. We can calculate midpoints as shown below.
mid1 = start + (end−start)/3
mid2 = end − (end−start)/3
- Compare the target element with mid1. If it is equal, return mid1.
- If not, compare the target element with mid2. If it is equal, return mid2.
- Compare the target element with mid1. If it is less, then recur to the first part.
- Compare the target element with mid2. If it is greater, then recur to the third part.
- Otherwise, recur to the middle part.
Code Example
public class TernarySearch {
public static int ternarySearch(int[] arr, int target) {
int start = 0;
int end = arr.length - 1;
while (start <= end) {
int mid1 = start + (end - start) / 3;
int mid2 = end - (end - start) / 3;
if (arr[mid1] == target) {
return mid1; // Target found at mid1
} else if (arr[mid2] == target) {
return mid2; // Target found at mid2
} else if (target < arr[mid1]) {
end = mid1 - 1; // Target is in the left third
} else if (target > arr[mid2]) {
start = mid2 + 1; // Target is in the right third
} else {
start = mid1 + 1;
end = mid2 - 1; // Target is in the middle third
}
}
return -1; // Target not found
}
public static void main(String[] args) {
int[] sortedRange = {1, 3, 5, 7, 9, 11, 13, 15, 19, 21, 33};
int target = 21;
int index = ternarySearch(sortedRange, target);
if (index != -1) {
System.out.println("Found the hidden treasure at index: " + index);
} else {
System.out.println("Treasure not found!");
}
}
}
Pros
- It is the optimal solution for locating maxima or minima in unimodal functions where binary search is not applicable. An unimodal function has a single peak or valley, and ternary search is particularly useful for finding the peak or valley in such functions.
- It involves fewer comparisons compared to binary search
Cons
- Works only on sorted arrays and doesn’t apply to unordered or non-linear datasets
- Less efficient compared to binary search for sorted data sets
Complexity
- Time Complexity: O(log3 n) = O(log n) — Similar to binary search, ternary search offers logarithmic time complexity in the best case. However, the exact complexity can vary depending on the data distribution.
- Space Complexity: The space complexity is O(1) because the solution involves constant space. In languages that support recursion, the space may go up logarithmically due to the system call stack, yielding a space complexity of O(log n).
The Smart Scale — Interpolation Search
Interpolation Search, an elegant and intelligent search algorithm, is like a wizard looking for a potion bottle on a shelf with the bottles organized by size. Instead of guessing where it could be, the wizard makes an educated guess based on understanding portion sizes. At its core, this approach is the idea behind Interpolation Search, making it an innovative and efficient search algorithm.
Interpolation search is an improvement over Binary Search, where values in a sorted array are uniformly distributed. Interpolation search generates new data points within the range of a known set of data points. Whereas Binary Search always goes to the middle element, Interpolation Search changes its seeking position based on the value of the searched key. If it is closer to the last element, for example, it’s most likely that Interpolation Search will start the search from the end portion of the array.
The dataset’s uniform distribution means the interval between the elements should be uniform (does not have a large difference).
Algorithm
> Start with the initial bounds (low and high).
> Estimate the position of the target using the formula:
> If the estimated position matches the target, return the index.
> If the target is smaller, repeat the search on the left subarray.
> If the target is larger, repeat the search on the right subarray.
> Continue searching until the target or the bounds cross each other.
Code Example
public class InterpolationSearch {
public static int interpolationSearch(int[] arr, int target) {
int low = 0;
int high = arr.length - 1;
while (low <= high && target >= arr[low] && target <= arr[high]) {
if (low == high) {
if (arr[low] == target) {
return low;
}
return -1;
}
// Estimate the position
int pos = low + ((target - arr[low]) * (high - low)) / (arr[high] - arr[low]);
// Check if the target is at the estimated position
if (arr[pos] == target) {
return pos;
}
// If target is larger, target is in the right subarray
if (arr[pos] < target) {
low = pos + 1;
} else {
// If target is smaller, target is in the left subarray
high = pos - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] sortedShelf = {1, 3, 5, 7, 9, 11, 13, 15, 17};
int targetBook = 11;
int index = interpolationSearch(sortedShelf, targetBook);
if (index != -1) {
System.out.println("Found the book at index: " + index);
} else {
System.out.println("Book not found!");
}
}
}
Pros
- More efficient than binary search for uniformly distributed data
- Efficient for large, sorted lists
Cons
- The performance degrades to O(n) if the data is not distributed uniformly.
- It is more complex to implement than binary and jump search
- Requires sorting the array.
Complexity
- Time Complexity: O(log log n) (average), O(n) (worst)
- Space Complexity: O(1) uses constant additional space regardless of the data set size.
The Expanding Explorer — Exponential Search
Imagine you’re searching for a book in a large, sorted bookshelf. Instead of linearly searching through each book, you increase your search range exponentially until you find a range where the book might be, then perform a binary search within that range. You’ve just performed an Exponential Search.
An exponential search algorithm targets a range of an input array, assuming that the required element must be present, and performs a binary search on that particular small range. This algorithm is also known as doubling search or finger search.
Algorithm
- Start from the first element in the sorted array.
- If the first element is the target, return the index.
- If the first element is not the target, find a range in which the target might be present. We do this by iterating through the array, starting from the first index and doubling the index at each step until we find an element greater than the target.
- Once we have the range, perform a binary search within that range for the target element.
Code Example
public class ExponentialSearch {
public static int exponentialSearch(int[] array, int target) {
int n = array.length;
// If target is present at first location itself
if (array[0] == target) {
return 0;
}
// Find range for binary search by repeated doubling
int i = 1;
while (i < n && array[i] <= target) {
i *= 2;
}
// Perform binary search within [i/2, min(i, n-1)]
return Arrays.binarySearch(array, i/2, Math.min(i, n), target);
}
public static void main(String[] args) {
int[] shelf = {1, 2, 3, 4, 5, 6, 7, 8, 9};
int targetBook = 6;
int result = exponentialSearch(shelf, targetBook);
if (result >= 0) {
System.out.println("Book found at index: " + result);
} else {
System.out.println("Book not found.");
}
}
}
Pros
- Efficient for large, sorted, unbounded lists
- Provides a quick initial estimate of the search range
- Combines the strengths of exponential range determination with binary search precision
Cons
- More complex than linear and binary searches
- Requires sorting the array.
- Inefficient for small arrays.
Complexity
- Time Complexity: O(log n) — It achieves a logarithmic time complexity due to its initial probing and subsequent binary search.
- Space Complexity: O(1) uses constant additional space regardless of the data set size.
Epilogue: Choosing Your Weapon
So, brave adventurers, which searching algorithm should you choose for your next quest? Here are some parting tips:
- Jump Search: Great for larger sorted lists when you want a balance between linear and binary search.
- Interpolation Search: Best for large, uniformly distributed sorted lists where you need maximum efficiency.
- Exponential Search: Efficient for large, sorted, unbounded lists when you need a quick initial estimate of the search range.
- Ternary Search: Suitable for sorted lists where the search space is efficiently divided into three parts.
Remember, the key to a successful search lies in knowing your data and choosing the right tool for the job.
Happy coding, and may you always find what you seek!
Stay classy!
