5 Important Search Algorithms

This post is also available in: हिन्दी (Hindi) العربية (Arabic)

In this article, we will be discussing the 5 Important Search Algorithms. Search and Sort Algorithms are an important part of almost all applications. Read the article and answer the questions in a quiz at the end.

What is a Search Algorithm?

A search algorithm is a step-by-step procedure used to locate specific data among a collection of data. It is considered a fundamental procedure in computing. In computer science, when searching for data, the difference between a fast application and a slower one often lies in the use of the proper search algorithm.

All search algorithms make use of a search key in order to proceed with the searching process. Search algorithms are expected to return a success or a failure status, usually denoted by Boolean true/false. Difference search algorithms are available, and the performance and efficiency of these algorithms depend on the volume of data and the manner in which they are used.

The two main critical factors apart from many others that are considered while selecting any algorithm are time and space. An algorithm should be such that it should take less time to carry out the task(time factor) and also the process should use minimum space(space factor).

Where Search Algorithms are Used?

Search algorithms are an important part of any application. When you make a call from your cell phone, the software present in it searches for a particular phone number and makes a call. Similarly, when you are typing a name on your favourite social media platform, the program searches for that name in its huge database. Nowadays everyone is aware of Search Engines like Google, Bing, etc. Search algorithms are a critical part of all these search engines. We cannot think of any application where search algorithms are not used in one or the other form.

Types of Search Algorithms

As mentioned above there are two important factors that are considered while selecting an algorithm. Depending on the requirement and volume of data, a particular search algorithm is selected for the purpose. Here we will discuss the 5 important search algorithms.

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

Linear Search

The first in our list of important search algorithms is Linear Search. Linear search is a very simple search algorithm. In this type of search, a sequential search is made over all items one by one. Every item is checked and if a match is found then that particular item is returned, otherwise, the search continues till the end of the data collection. If the item is not found till the end of data collection, the algorithm returns a boolean value ‘false’ meaning item not found.

How Does A Linear Search Works?

The linear search follows the following steps:

  • Initialize boolean variable to false.
  • Start from the leftmost (first) element of an array and one by one compare the element we are searching for with each element of the array.
  • If there is a match between the element we are searching for and the current element of the array, return the position of the element and make a boolean variable found = true.
  • If found = false, then the element is not found.
Algorithm for Linear Search

Step 1: Set i to 1

Step 2: if i > n then go to step 7

Step 3: if A[i] = x then go to step 6

Step 4: Set i to i + 1

Step 5: Go to Step 2

Step 6: Print Element x Found at index i and go to step 8

Step 7: Print element not found

Step 8: Exit

Code for Linear Search in C++
int search(int arr[], int n, int x)
{
    int i;
    for (i = 0; i < n; i++)
        if (arr[i] == x)
            return i;
    return -1;
}
int main()
{
    int arr[] = { 3, 4, 1, 7, 5 };
    int n = sizeof(arr) / sizeof(arr[0]);
    int x = 4;
    int index = search(arr, n, x);
    if (index == -1)
        cout << "Element is not present in the array";
    else
        cout << "Element found at position " << index;
    return 0;
}

Binary Search

Binary search is a widely used algorithm for sorted data and hence is another in the list of important search algorithms. A binary search is an advanced type of search algorithm that finds and fetches data from a sorted list of items. Its core working principle involves dividing the data set in the list into half until the required item is located and returned. Binary search is also sometimes called half-interval search or a logarithmic search.

How Does A Binary Search Works?

The binary search follows the following steps:

The search process initiates by locating the middle element of the sorted array of data

  • Initialize boolean variable to false.
  • The key value is compared with the current element.
  • If the key value is greater than the middle element, then search analyses the upper values to the middle element for comparison and matching.
  • In case the key value is smaller than the middle element, then search analyses the lower values to the middle element for comparison and matching.
  • In case the key value is equal to the middle element, return the position of the current element, and make the boolean variable found = true.
  • If found = false, then the element is not found.
Algorithm for Binary Search

Step 1: Set L to 0 and U to N and F to ‘False’

Step 2: MID = (L + U)/2

Step 3: if A[MID] = x, then Print Element  x Found at index MID and set F to ‘True’ and goto step 6 

Step 4: if A[MID] > x, U = MID – 1 and goto step 2

Step 5: if A[MID] < x, L = MID + 1 and goto step 2

Step 6: If F = ‘False’ then Print Element x Not Found 

Step 7: Exit

Code for Binary Search in C++
int binarySearch(int arr[], int l, int r, int x)
{
    if (r >= l) {
        int mid = l + (r - l) / 2;
        if (arr[mid] == x)
            return mid;
        if (arr[mid] > x)
            return binarySearch(arr, l, mid - 1, x);
        return binarySearch(arr, mid + 1, r, x);
    }
      return -1;
}
int main(void)
{
    int arr[] = { 2, 3, 4, 10, 40 };
    int x = 10;
    int n = sizeof(arr) / sizeof(arr[0]);
    int result = binarySearch(arr, 0, n - 1, x);
    (result == -1) ? cout << "Element is not present in array"
                   : cout << "Element is present at index " << result;
    return 0;
}

Jump Search

Like Binary Search, Jump Search is a searching algorithm for sorted arrays. The basic idea is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in place of searching all elements. That’s the reason it occupies a place in a list of important search algorithms

Let’s consider a sorted array A of size n, with index ranging from 0 to n-1, and element x that needs to be searched in the array A. For implementing this algorithm, a block of size m is also required, that can be skipped or jumped in every iteration.

How Does A Jump Search Works?

The algorithm works as follows:

  • Iteration 1: if x = A[0], then success, else if x > A[0], then jump to the next block.
  • Iteration 2: if x = A[m], then success, else, if x > A[m], then jump to the next block.
  • Iteration 3: if x = A[2m], then success, else, if x > A[2m], then jump to the next block.
  • At any point in time, if x < A[km], then a linear search is performed from from position A[(k – 1)m] to A[km]
Algorithm for Jump Search

Step 1: Set i = 0 and m = sqrt(n).

Step 2: if A[i] != x and A[i] < x, then jump to the next block and set i = m and m = m + m.

Step 3: if m < n – 1 then goto step 2

Step 4: if A[i] > x, then move to the beginning of the current block and perform a linear search.

Step 5: Exit

Code for Jump Search in C++
int jumpSearch(int array[], int size, int key) {
   int start = 0;
   int end = sqrt(size);
   while(array[end] <= key && end < size) {
      start = end; 
      end += sqrt(size);
      if(end > size - 1)
         end = size; 
   }
   for(int i = start; i<end; i++) 
      if(array[i] == key)
         return i; 
   }
   return -1;
}
int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n];
   cout << "Enter items: " << endl;
   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }
   cout << "Enter search key to search in the list: ";
   cin >> searchKey;
   if((loc = jumpSearch(arr, n, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

Interpolation Search

Interpolation Search is another important search algorithms. Interpolation Search is an improved variant of Binary Search. This search algorithm works on the probing position of the required value. For this algorithm to work properly, the data collection should be in a sorted form and equally distributed.

There are cases where the location of target data may be known in advance. For example, in case of a telephone directory, if we want to search the telephone number of a particular person having name starting with ‘M’. Here, linear search and even binary search seem slow as we can directly jump to memory space where the names start from ‘M’ are stored.

In case of binary search, if the desired data is not found then the rest of the list is divided into two parts, lower and higher. Then the search is carried out in either of them. Even if the data is sorted, binary search does not take advantage to probe the position of the desired data.

How Does An Interpolation Search Works?

The algorithm works as follows:

  • Interpolation search finds a particular item by computing the probe position. Initially, the probe position is the position of the middlemost item of the collection.
  • If a match occurs, then the index of the item is returned. To split the list into two parts, we use the following method:

mid = Lo + ((Hi – Lo)/(A[Hi] – A[Lo])) * (x – A[Lo]), where

A is list

Lo is lowest index of the list

Hi is highest index of the list

A[n] is the value stored at index n in the list 

  • If the middle item is greater than the item x, then the probe position is again calculated in the sub-array to the right of the middle item. Otherwise, the item is searched in the sub-array to the left of the middle item. This process continues on the sub-array as well until the size of the sub-array reduces to zero.
Algorithm for Interpolation Search

Step 1: Start searching data from the middle of the list and initialize boolean variable F to ‘False’.

Step 2: If it is a match, return the index of the item and move ‘True’ to F goto 

Step 3: If it is not a match, probe position.

Step 4: Divide the list using a probing formula and find the new middle.

Step 5: If the data is greater than middle, search in higher sub-list.

Step 6: If data is smaller than middle, search in lower sub-list.

Step 7: If F = ‘False’ then Print Element x Not Found

Step 8: Exit

Code for Interpolation Search in C++
int interpolationSearch(int array[], int start, int end, int key) {
   int dist, valRange, indexRange, estimate;
   float fraction;
   while(start <= end && key >= array[start] && key <= array[end]) {
      dist = key - array[start];
      valRange = array[end] - array[start];
      fraction = dist / valRange;
      indexRange = end - start;
      estimate = start + (fraction * indexRange);
      if(array[estimate] == key)
         return estimate;
      if(array[estimate] < key)
         start = estimate +1;
      else
         end = estimate - 1;
   }
   return -1;
}
int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n];
   cout << "Enter items: " << endl;
   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }
   cout << "Enter search key to search in the list: ";
   cin >> searchKey;
   if((loc = interpolationSearch(arr, 0, n-1, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

Exponential Search

The next in the list of important search algorithms is 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 present. If L and U are the lower and upper bounds 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 this 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.

Algorithm  for Exponential Search

Step 1: Jump the array 2^i elements at a time searching for the condition Array[2^(i-1)] < valueWanted < Array[2^i].

Step 2: If 2^i is greater than the length of the array, then set the upper bound to the length of the array.

Step 3: Do a binary search between Array[2^(i-1)] and Array[2^i]

Code for Exponential Search in C++
int binarySearch(int array[], int start, int end, int key) {
   if(start <= end) {
      int mid = (start + (end - start) /2);
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}
int exponentialSearch(int array[], int start, int end, int key){
   if((end - start) <= 0)
      return -1;
      int i = 1; 
      while(i < (end - start)){
         if(array[i] < key)
            i *= 2; 
         else
            break;
   }
   return binarySearch(array, i/2, i, key); 
}
int main() {
   int n, searchKey, loc;
   cout << "Enter number of items: ";
   cin >> n;
   int arr[n];
   cout << "Enter items: " << endl;
   for(int i = 0; i< n; i++) {
      cin >> arr[i];
   }
   cout << "Enter search key to search in the list: ";
   cin >> searchKey;
   if((loc = exponentialSearch(arr, 0, n, searchKey)) >= 0)
      cout << "Item found at location: " << loc << endl;
   else
      cout << "Item is not found in the list." << endl;
}

[tqb_quiz id=’2545′]

Image Credit: Computer vector created by pch.vector – www.freepik.com

Leave a Comment