Searching Algorithms: Linear, Binary, Jump, and Interpolation Search

In programming, searching algorithms are used to retrieve information or data stored in a data structure. These are some of the most commonly used algorithms implemented in any program or application. There are various types of programs like word processors, database management systems (DBMS), and even operating systems. All have some search functionality built in that the end users can use.

Types of Search Algorithms

There are various algorithms used to implement search functionality that differs in their working. Some of the most common search algorithms are

1. Linear Search
2. Binary Search
3. Jump Search
4. Interpolation Search

1. Linear Search

Linear search is one of the most basic search algorithms. A sequential searching algorithm looks through the entire data structure to find the required item or information.

It starts from one end of the data structure and looks through every element stored until the required item is found. Otherwise, it traverses the entire data structure and stops.

#include <iostream>
using namespace std;

bool LinearSearch(int* arr, int size, int key) {
	for (int i = 0; i < size; i++) {
		if (arr[i] == key) {
			return true;
		}
	}
	return false;
}

int main() {
	int arr[10] = { 8, 12, 23, 34, 47, 58, 61, 80, 99, 101 };
	cout << "Linear Search 99 : " << LinearSearch(arr, 10, 99) << endl;
	
	return 0;
}

Output: Linear Search Algorithm

Code Explanation

• Line#4: Defines the header for our function including its name, return type, and parameters.
• Line#5: Initializes a for loop that iterates from the start of the array to the last index.
• Line#6: Uses an if condition to check if the current element in the array matches the key.
• Line#7: Returns true if the current element matches the key.
• Line#10: Returns false if no match is found in the array.
• Line#14: Defines a static array arr with some data values.
• Line#15: Invokes LinearSearch(arr, 10, 99) function while 10 as the size of the array and 99 as the key to search & print the result.

Time Complexity

Since linear search traverses the entire data structure, its worst-case time analysis is O(n) where n shows the number of items in a linear array.

Binary Search

Binary search is an interval-based searching algorithm that divides the data into smaller intervals and searches for the required element in those intervals rather than searching through an entire data structure. However, this algorithm requires that the data structure must be sorted in some order.

In each turn, the algorithm checks the middle element of the data structure and based on that element, it either searches the right half of the data structure, and the left half of the data structure or stops if the middle element is a match.

#include <iostream>
using namespace std;

bool BinarySearch(int* arr, int low, int high, int key) {
	if (low >= high) {
		return false;
	}
	else {
		int mid = (high + low) / 2;
		if (arr[mid] == key) {
			return true;
		}
		else if (arr[mid] > key) {
			return BinarySearch(arr, low, mid, key);
		}
		else {
			return BinarySearch(arr, mid + 1, high, key);
		}
	}
}

int main() {
	int arr[10] = {8, 12, 23, 34, 47, 58, 61, 80, 99, 101};
	cout << "Binary Search 99 : " << BinarySearch(arr, 0, 10, 99) << endl;
	return 0;
}

Output: Binary Search Algorithm

Code Explanation:

• Line#4: Defines the signature for the binary search function including its name, return type, and parameters.
• Line#5: Defines the base case of our recursive function which is used to break the recursion. Here, recursion is broken whenever the lower index matches or exceeds the last index.
• Line#9: Calculates the middle index mid of the array.
• Line#10: Check if the element at the middle index matches the key or not. If it matches, then the function returns true.
• Line#14: Sends a recursive call to search the right half of the array if the element at the middle index is greater than the key.
• Line#17: Sends a recursive call to search the left half of the array if the element at the middle index is smaller than the key.
• Line#22-26: main() method to drive BinarySearch() function.

Time Complexity

As this algorithm divides the data structure into halves after each interval, its time complexity is reduced compared to linear search. The worst-case time complexity of the binary search is O(log n), where n is the no. of elements in a data structure.

Jump Search

Jump search is also an interval-based searching algorithm. The data structure must be sorted for this algorithm as well. It works by comparing with an element in the data structure and then jumping by a fixed size m.

If the starting index is 0, then it will search indices 0, m, 2m, …, km in the data structure once it finds a range of indices such that array[km] < x < array[(k+1)m] where x is the required data, then it performs a linear search starting from index km to index (k+1)m.

#include <iostream>
#include <math.h>
using namespace std;

bool JumpSearch(int *arr, int size, int key)
{
    int step_size = 0, prev_step = 0;

    while (arr[step_size] < key)
    {
		// if the last element of the array is smaller 
        // than the key then the key does not exist in the array
		if (step_size == size - 1) {
			return false;
		}

        prev_step = step_size;
        step_size += sqrt(size);

		if (step_size >= size)
			step_size = size - 1;
    }

	int last_index = min(step_size, size);
    while (prev_step <= last_index)
    {
		if (arr[prev_step] == key) {
			return true;
		}
		prev_step++;
    }

    return false;
}
// main function
int main() {
	int arr[10] = { 8,12,23,34,47,58,61,80,99,101 };
	cout << "Jump Search 99 : " << JumpSearch(arr, 10, 99) << endl;
	return 0;
}

Output: Jump Search Algorithm

Code Explanation

• Line#5: Defines the signature of JumpSearch() function including its name, return type, and parameters.
• Line#7: Defines two variables that are used to store the current step size and previous step size of the array segment being searched.
• Line#9: Defines the while loop used to find the segment of the array which contains the key required. Loop will continue until it encounters an element larger than the key. In the array used as an example, the size of the array is 10 and its square root is approximately 3. Thus, the loop will first check arr[0], then arr[3], then arr[6], and finally arr[9]. As arr[9] == key thus the loop will break. At the end of the loop, prev_step = 6 and step size = 9. These indicate the starting and ending index of the segment which can contain the key.
• Line#24: Stores the last index for the linear search in a separate variable. Min(step_size, size) is used in case the step_size is exceeding the actual size of the array.
• Line#25-29: Perform a linear search starting from prev_step to last_index. If the key is found in this region of the array, then true is returned.
• Line#33: Returns false if the key is not found in the linear search performed above.

Time Complexity

The worst-case time complexity of this algorithm is O(sqrt(n)). However, to achieve this time complexity the jump size m must be sqrt(n).

Interpolation Search

It is an improvement of binary search and also requires the data structure to be ordered. The only difference is that rather than checking the middle element of the data structure.

Then dividing the interval, we search data[pos] where data is the name of our data structure and pos is the index to be searched.

It is given by pos = low + (x - data[low]) *(hi - low)/(data[hi] - data[low]), where low is the starting index and hi is the ending index of the interval being searched.

#include <iostream>
using namespace std;

bool InterpolationSearch(int* arr, int size, int key) 
{
	int low = 0, high = size - 1;
	while (low <= high && arr[low] <= key && key <= arr[high]) {
		if (low == high) {
			if (arr[low] == key) {
				return true;
			}
			else {
				return false;
			}
		}
		int position = low + ((((double)(high - low)) * (key - arr[low])) / (arr[high] - arr[low]));

		if (arr[position] == key) {
			return true;
		}
		else if (arr[position] < key) {
			low = position + 1;
		}
		else {
			high = position - 1;
		}
	}
}

int main() {
	int arr[10] = { 8,12,23,34,47,58,61,80,99,101 };
	cout << "Interpolation Search 99 : " << InterpolationSearch(arr, 10, 99) << endl;
	return 0;
}

Output: Interpolation Search Algorithm

Code Explanation

• Line#4: defines the header for our function including its name, return type, and parameters.
• Line#6: defines the starting and ending index of the searched segment. Initially, the segment is the entire array.
• Line#7: defines the while loop used to find the segment of the array which contains the key required. Loop will continue as long as the starting index does not exceed the ending index and the key required falls in the range of arr[low], arr[high].
• Line#8: checks if the starting and ending indices of the segment are the same, meaning the segment has been reduced to a single element.
• Line#10: returns true if the last remaining element is the key required. Else Line #13 returns false.
• Line#16: calculates the value of the position variable using the formula given above.
• Line#18: checks if the value at the index stored in position is the key. If it is the key, it returns true, else it updates the starting or ending index of the segment and continues the process.

Time Complexity

The average time complexity of this algorithm is O(log(log n)) and the worst-case time complexity is O(n).