Chapter Twenty-One: Searching Algorithms
A searching algorithm is designed to look for an element or print the same element from the program's data structures or variables. There are numerous algorithms you can use to search for elements in the structures. The algorithms are classified into the following categories:
●     Interval search : An interval search is one where the algorithm will look for the element in a sorted structure. These algorithms are better to use when compared to the next category since the structure is broken down and divided into parts before the element is identified in the structure—for example, binary search.
●     Sequential search : In these types of algorithms, the compiler moves from one element to the next to look for the element in the data structure. An example of this algorithm is linear search.
Let us look at how these search algorithms work in C++.
Linear Search
Let us understand how the search algorithm works in C++ using an example. Consider a problem where you have an array ‘arr[]’ with n elements; how would you look for the value ‘x’ in the arr[]?
Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 110;
Output : 6
Element x is present at index 6
Input : arr[] = {10, 20, 80, 30, 60, 50,
110, 100, 130, 170}
x = 175;
Output : -1
Element x is not present in arr[].
The simplest way to perform a linear search is as follows:
  1. Begin at the end of the array and compare the element you are looking for against each array element.
  2. If the element matches one of the elements in your array, return the index
  3. If the element does not match, move to the next element
  4. If the element is not present in the array, return -1.
// C++ code to linearly search x in arr[]. If x
// is present then return its location, otherwise
// return -1
#include <iostream>
using namespace std;
int search(int arr[], int n, int x)
{
int i;
for (i = 0; i < n; i++)
if (arr[i] == x)
return i;
return -1;
}
// Driver code
int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int x = 10;
int n = sizeof(arr) / sizeof(arr[0]);
// Function call
int result = search(arr, n, x);
(result == -1)
? cout << "Element is not present in array"
: cout << "Element is present at index " << result;
return 0;
}
Binary Search
As mentioned earlier, a binary search is based on the interval search algorithm, where you look for an element in a sorted array. When compared to a linear search algorithm, a binary search algorithm has a higher time complexity.
A binary search uses the whole array as the interval when the search starts. It then breaks the interval into parts to look for the search element. It divides the array into half and looks for the element in the array's lower and upper sections. Depending on where the element lies, the algorithm will break the interval into a smaller section to look for it. It continues to do this until it finds the element.
A binary search aims to use the existing information in the array after it sorts the elements. This reduces the time complexity of the algorithm to O (log n). In a binary search, half the elements are not considered after making one comparison.
  1. Sort the array.
  2. Compare the search element x with the element in the middle of the array.
  3. If x is less than the middle element, ignore the right section of the array since x can only lie in the left section of the array.
  4. We then perform the same functions with the left section of the array.
  5. If x is greater than the middle element in Step 3, we consider the array's right section.
We will now look at two ways to implement the binary search algorithm: recursive and iterative.
Before that, let us understand the time complexity of the binary search algorithm. You can calculate the time complexity of an algorithm using the following formula: T(n) = T(n/2) + c
You can remove the recurrence by using a master or recurrence tree method.
Recursive Implementation
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// a recursive binary search function. It returns
// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;
// If the element is present at the middl e
// itself
if (arr[mid] == x)
return mid;
// If element is smaller than mid, then
// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);
// Else the element can only be present
// in right subarray
return binarySearch(arr, mid + 1, r, x);
}
// We reach here when element is not
// present in array
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;
}
The output of the code is:
Element is present at index 3
Iterative Implementation
// C++ program to implement recursive Binary Search
#include <bits/stdc++.h>
using namespace std;
// a iterative binary search function. It returns
// location of x in given array arr[l..r] if present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)
return m;
// If x greater, ignore left half
if (arr[m] < x )
l = m + 1;
// If x is smaller, ignore right half
else
r = m - 1;
}
// if we reach here, then element was
// not present
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;
}
The output of the code is: Element is present at index 3
Jump Search
The jump search algorithm is similar to the binary search algorithm in the sense that it looks for the search element in a sorted array. This algorithm's objective is to search for the search element from fewer elements in the array. The compiler can jump ahead by skipping a few elements or jumping ahead by a few steps.
Let us understand this better using an example. Suppose you have an array with n elements in it, and you need to jump between the elements by m fixed steps. If you want to look for the search element in the array, you begin to look at the following indices a[0], a[m], a[2m], ….. a[km]. When you find the interval where the element may be, the linear search algorithm kicks in.
Consider the following array: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). The length of this array is 16. Let us now look for element 55 in the array. The block size is 4, which means the compiler will jump four elements each time.
Step 1: The compiler moves from index 0 to 3.
Step 2: The compiler moves from 4 to 8.
Step 3: The compiler jumps from 9 to 12.
Step 4: The element in position 12 is larger than 55, so we go back to the previous step.
Step 5: The linear search algorithm kicks in and looks for the index of the element.
Optimal Block Size
When you use the jump search algorithm, you need to choose the right block size, so there are no issues in the algorithm. In the worst-case scenario, you need to perform n/m jumps. If the element the compiler last checked was greater than the search element, you need to perform m-1 comparisons when the linear search algorithm kicks in. Therefore, in the worst-case scenario, the number of jumps should be ((n/m) + m-1). This function's value will be minimum if the value of the element ‘m’ is square root n. The step size, therefore, should be m = √n.
// C++ program to implement Jump Search
#include <bits/stdc++.h>
using namespace std;
int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);
// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] < x)
{
prev = step;
step += sqrt(n);
if (prev >= n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++ ;
// If we reached next block or end of
// array, element is not present.
if (prev == min(step, n))
return -1;
}
// If element is found
if (arr[prev] == x)
return prev;
return -1;
}
// Driver program to test function
int main()
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610 };
int x = 55;
int n = sizeof(arr) / sizeof(arr[0]);
// Find the index of 'x' using Jump Search
int index = jumpSearch(arr, x, n);
// Print the index where 'x' is located
cout << "\nNumber " << x << " is at index " << index ;
return 0;
}
The output of this code: Number 55 is at index 10
Some important points to note about this algorithm are:
●      This algorithm only works when an array is sorted
●     Since the optimal length the compiler should jump is √ n, the time complexity of this algorithm is O (√ n). This means the time complexity of this algorithm is between the binary search and linear search algorithms
●     The jump search algorithm is not as good as the binary search algorithm, but it is better than the binary search algorithm since the compiler only needs to move once back through the array. If the binary search algorithm is too expensive, you should use the jump search algorithm.