Searching Algorithms

The purpose of Searching Algorithms is to give users the ability to check for an element or retrieve an element from the data structure where it’s stored.

Two Common Types of Search Algorithms
1. Sequential Search: The list or array is traversed sequentially and every element is checked; example: Linear Search
2. Interval Search: In sorted data structures, these algorithms are able to search more efficiently than sequential searches because they’re able to target the center of the search structure and divide the search space in half; example: Binary Search

Linear Search Example
Difficulty: Basic

Problem: Given an array arr[] of n elements, write a function to search a given element x in arr[].

A simple approach is to start from the leftmost element of arr[] and loop through the array to check for a match with the value of interest. If true, return the index and if not, be able to indicate so.

Considerations: The time complexity of this algorithm is O(n), as the array needs to traverse through each element in the array, and since there are other algorithms which are able to search much more quickly, as the input size n increases, scaling using this algorithm becomes less and less ideal.

Binary Search Example
Difficulty: Easy

Problem: Given a sorted array arr[] of n elements, write a function to search a given element x in arr[].

This is the same task as above, but the approach towards finding the element of interest changes. The procedure starts with searching a sorted array by repeatedly dividing the search interval in half. Begin with an interval covering the whole array. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Continue repeating this process until the value is found or the interval is empty.

Considerations: Using this algorithm reduces the average time complexity to O(logn) and the space complexity would be O(1) since no memory would be allocated towards finding the element of interest.

Jump Search Algorithm
Difficulty: Easy

Like Binary Search, Jump Search is used for sorted arrays aiming to “jump” through elements in “blocks”, rather than traversing every single one in the array. When the algorithm finds an interval that is past the value of the element of interest, then a linear search is implemented the traverse the local area until the element of interest is located.

Considerations: In the worst case, n/m jumps would need to be done if the value is at the end of the array. In terms of time complexity, this algorithm is between Linear Search and Binary Search. The best step size is m = √n.

Interpolation Search
Difficulty: Easy

Compared to Binary Search, Interpolation Search can vary where it starts its initial search (Binary Search starts at the middle of the sorted dataset). The position (pos) in the dataset the algorithm starts from will depend on whether the element to be searched is closer to arr[high] or arr[low]. The formula to find the pos can be found here.

Exponential Search
Difficulty: Easy

In Exponential Search, the range where the element is present is found, and then using that found range, a Binary Search is executed. The range is initiated with a subarray size of 1 and compared to the value of the element of interest. If the range does not the element of interest value, the array size is doubled until the value of interest is held in the range, hence the name Exponential Search. The time complexity of this algorithm is O(logn) and the auxiliary space necessary for this search is O(logn) space, which is more space than Binary Search, which only requires O(1) space.

More Search Algorithms
https://www.geeksforgeeks.org/searching-algorithms/#algo
Go to “Search Algorithms” and start from Exponential Search

Sublist Search
Difficulty: Easy

Given two linked lists, the task is to check whether the first list is present in the second list or not. The algorithm requires multiple steps which include:
1. Take the first node of the second list
2. Start matching the first list from the first node
2A. If the whole lists match, return true
2B. Else, break and take the first list to the first node again
3. Take the second list to its second node
4. Repeat until the first linked list becomes empty

The time complexity of this algorithm is O(m*n) where m is the number of nodes in the second list and n is the first.

Fibonacci Search
Difficulty: Medium

In this algorithm, given a sorted array of size n and element x to be searched and return the index of x if present.

The Fibonacci Search is a comparison-based technique that uses Fibonacci numbers to search an element in a sorted array. It is similar to Binary Search because it works only for sorted arrays and has a divide and conquer approach with a O(logn) time complexity. However, it differs from Binary Search because the array is divided into unequal parts.

Sources

https://www.geeksforgeeks.org/searching-algorithms/#algo
https://www.geeksforgeeks.org/binary-search/
https://www.geeksforgeeks.org/jump-search/