Searching algorithms help us find elements efficiently in data structures like arrays and linked lists. In this blog, we will explain five important searching algorithms in an easy-to-understand way: Linear Search, Binary Search, Jump Search, Interpolation Search, and Exponential Search.
Types of Searching Algorithms
Two major categories may be used to group searching algorithms:
- Linear Search
- Binary Search
- Jump Search
- Interpolation Search
- Exponential Search
- Fibonacci Search
- Hashing-based Search
- Tree-based Search
1. Linear Search (O(n))
Linear Search is the simplest searching method. Until it discovers the necessary element or reaches the end, it iteratively traverses through each element in the array.
How it Works:
1. Begin with the array’s first entry.
2. Examine it in relation to the desired element.
3. Return the index if they match.
4. If not, repeat with the following element.
5. Return -1 if the array’s end is reached and no match is discovered.
Example:
Imagine searching for 30 in the array [10, 20, 30, 40, 50]. One by one, you examine each component until you locate thirty.
class LinearSearch {
static int search(int arr[], int key) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == key)
return i;
}
return -1;
}
}
Code Explanation:
- The loop runs through each element in the array.
- The index is returned if the key is located.
- It returns -1 if the key cannot be located.
2. Binary Search (O(log n))
Binary Search is a faster method that works only on sorted arrays. Rather than going over each element individually, it continually splits the array in half and looks in the right half.
How it Works:
- Locate the array’s center member.
- Return the index if it matches the key.
- Look at the left part of the key if it is smaller.
- Look in the right side of the key if it is larger.
- Repeat until you find the element or the array is empty.
Example:
Searching for 40 in [10, 20, 30, 40, 50]:
- Check middle (30) → 40 is larger → Search right half.
- Check middle (40) → Found!
class BinarySearch {
static int search(int arr[], int left, int right, int key) {
while (left <= right) {
int mid = left + (right – left) / 2;
if (arr[mid] == key)
return mid;
if (arr[mid] < key)
left = mid + 1;
else
right = mid – 1;
}
return -1;
}
}
Code Explanation:
- The middle element is calculated.
- If the key is found, return its index.
- Otherwise, continue searching in the appropriate half.
3. Jump Search (O(√n))
Jump Search operates on sorted arrays and is quicker than Linear Search. It advances a predetermined number of steps rather than inspecting each piece individually.
How it Works:
- Choose a step size of √n (square root of array size).
- Jump forward by that step size until you go past the key.
- Do a Linear Search in the last block.
Example:
Searching for 30 in [10, 20, 30, 40, 50, 60]:
- Jump 2 steps: [10 → 30] → Found!
class JumpSearch {
static int search(int arr[], int key) {
int n = arr.length;
int step = (int) Math.sqrt(n);
int prev = 0;
while (arr[Math.min(step, n) – 1] < key) {
prev = step;
step += (int) Math.sqrt(n);
if (prev >= n)
return -1;
}
for (int i = prev; i < Math.min(step, n); i++) {
if (arr[i] == key)
return i;
}
return -1;
}
}
Code Explanation:
- The array is divided into blocks.
- The algorithm jumps ahead by √n until it overshoots the key.
- A linear search is then performed within the last block.
4. Interpolation Search (O(log log n))
Interpolation Search is an advanced version of Binary Search that predicts where the key might be instead of always checking the middle.
How it Works:
- Use a formula to estimate the key’s location.
- Check if the key is at that position.
- If not, adjust the range and repeat.
Example:
If searching for 40 in [10, 20, 30, 40, 50], instead of checking the middle, it estimates that 40 is near the end.
class InterpolationSearch {
static int search(int arr[], int key) {
int low = 0, high = arr.length – 1;
while (low <= high && key >= arr[low] && key <= arr[high]) {
int pos = low + ((key – arr[low]) * (high – low)) / (arr[high] – arr[low]);
if (arr[pos] == key)
return pos;
if (arr[pos] < key)
low = pos + 1;
else
high = pos – 1;
}
return -1;
}
}
Code Explanation:
- It estimates the probable position of the key based on the values in the array.
- If the key is found, return its index.
- Otherwise, update the search range and repeat.
5. Exponential Search (O(log n))
Exponential Search is useful when the array size is unknown. It doubles the search range until it finds an upper bound, then applies Binary Search.
How it Works:
- Start with the first element.
- Keep doubling the index until the key is smaller.
- Apply Binary Search in the identified range.
Example:
Searching for 50 in [10, 20, 30, 40, 50, 60, 70]:
- Check index 1 → 20 (too small)
- Check index 2 → 30 (too small)
- Check index 4 → 50 (Found!)
class ExponentialSearch {
static int search(int arr[], int key) {
int n = arr.length;
if (arr[0] == key)
return 0;
int i = 1;
while (i < n && arr[i] <= key)
i *= 2;
return BinarySearch.search(arr, i / 2, Math.min(i, n – 1), key);
}
}
Code Explanation:
- The search range doubles at each step.
- Binary Search is used once the range has been identified.
Conclusion
Searching algorithms are the backbone of data retrieval systems. Selecting the optimal strategy for various use cases is made easier by being aware of its advantages and disadvantages. While Linear Search is simple, Binary Search, Jump Search, and Interpolation Search offer faster performance for sorted datasets. Advanced techniques like Exponential and Fibonacci Search improve efficiency in specialized scenarios.
For students and professionals, mastering these algorithms is essential for writing efficient programs and acing coding interviews.
Choosing the right searching algorithm depends on the situation:
- Linear Search is simple but slow.
- Binary search is quick, but it needs an array that has been sorted.
- Jump Search speeds up searching in sorted data.
- Interpolation Search is useful when data is uniformly distributed.
- Exponential Search is great for large or unknown-sized arrays.
Knowing these algorithms will help you select the one that best suits your requirements!
