SEARCHING ALGORITHMS

Searching algorithms is a basic, vital step in computing. It is a step-by-step technique to locate a particular data among a collection of data.

In computer science, there are various type of search algorithms available. The way they perform their activity decides the performance and efficiency of the manner in which the data is being used.

These algorithms are mainly categorised in 2 categories on the basis of their type of search operations. The two categories are:

  1. Sequential Search: In this, the list or array is tracked sequentially and every element is checked. For example: Linear Search
  1. Interval Search: These algorithms are precisely designed for searching in organized data-structures. These type of searching algorithms are more efficient than Sequential Search method, as they repetitively target the centre of the search structure and divide the search space in 2 halves. For Example: Binary Search.

Few of the searching algorithms are:

  • Linear Search
  • Binary Search
  • Jump Search
  • Interpolation Search
  • Exponential Search
  • Linear Search:

A linear search or sequential search is a technique for finding an element within a list. This type of searching algorithms sequentially checks each element of the list until a match is found or the whole list has to be searched.

A linear search runs in at worst linear time and makes at most n comparisons, where n is the length of the list. The time complexity of this algorithm is O(n).

  • Binary Search:

This type of searching algorithms is used to find the location of a specific value contained in a sorted array. Binary search algorithm works on the principle of divide & conquer and it is considered the best searching algorithms because of its rapid speed to search (Provided the data is in sorted form). A binary search is also known as a half-interval search or logarithmic search. The time complexity of above algorithm is O(log n).

  • Jump Search:

Just like Binary Search, this algorithm is one of the searching algorithms for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or avoiding some elements in place of searching all elements. The time complexity of this algorithm is between linear search (O(n)) and Binary Search (O(Log n)).

  • Interpolation Search:

Interpolation search is an upgraded variant of binary search. This search algorithm works on the searching position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed. Interpolation search is that type of searching algorithms, used for searching for a key in an array that has been ordered by numerical values assigned to the elements (key values). Time Complexity: O(log2(log2 n)) for the average case, and O(n) for the worst case (when items are distributed exponentially)

  • Exponential Search:

Exponential search is also known as doubling or galloping search. This mechanism is used to find the range where the search key may exist.

If L and U are the upper and lower bound of the list, then L and U both are the power of 2. For the last section, the U is the last position of the list. For that reason, it is known as exponential. After finding the specific range, it uses the binary search technique to find the exact location of the search key.