Introduction To Searching Algorithms In C++

An Overview Of Searching Algorithms In C++.

We keep searching for something or the other in our everyday life. Just like our everyday life, as a software professional, we need to search for information on our computer. Information retrieval should be done fast as we cannot afford to waste much of our time searching for information.

Hence we need some efficient searching techniques or algorithms that can search a given piece of information in a short time and give to the user so that the user can go ahead with the other tasks.

=> Visit Here For The Complete C++ Tutorials list.

SEARCHING ALGORITHMS IN C++

Searching Techniques

We have two main searching techniques that are mostly employed to search for information.

These include:

  • Linear Search
  • Binary Search

In this tutorial, we will explore both of these search techniques in detail.

Linear Search

This is the most basic searching technique and is easier to implement too. In a linear search, the key to be searched is compared linearly with every element of the data collection. This technique works effectively on linear data structures.

Let us consider the following array.

Linear Search array

Above is the array of seven elements. If we want to search key = 23, then starting from the 0th element, the key value will be compared to each element. Once the key element matches with the element in the array, then that particular location will be returned. In this case location, 4 will be returned as the key-value matches the value at that location.

We have implemented a linear search using C++ and Java language below.

C++ Implementation

#include <iostream>
#include <string>
using namespace std;
int main()
{
   int myarray[10] = {21,43,23,54,75,13,5,8,25,10};  
    int key,loc;
    cout<<"The input array is"<<endl;
    for(int i=0;i<10;i++){
        cout<<myarray[i]<<" ";
    }
    cout<<endl;
    cout<<"Enter the key to be searched : "; cin>>key;
    for (int i = 0; i< 10; i++)  
    {  
        if(myarray[i] == key)   
        {  
            loc = i+1;
            break;  
        }   
        else   
        loc = 0;  
    }   
    if(loc != 0)  
    {  
        cout<<"Key found at position "<<loc<<" in the array";  
    }  
    else  
    {  
        cout<<"Could not find given key in the array";  
    }  
  
}

Output:

The input array is
21 43 23 54 75 13 5 8 25 10
Enter the key to be searched : 3
Could not find given key in the array

The input array is
21 43 23 54 75 13 5 8 25 10
Enter the key to be searched: 75
Key found at position 5 in the array

Java Implementation

import java.util.*;
import java.lang.*;
import java.io.*;
public class Main
{       public static void main(String[] args) {
        int[] myarray = {21,43,23,54,75,13,5,8,25,10};  
        int key,location=0;   
        Scanner sc = new Scanner(System.in);  
        System.out.println("The input array is");
        for(int i=0;i<10;i++){
            System.out.print(myarray[i]+" ");
        }
        System.out.println("\n");
        System.out.println("Enter key");  
        key = sc.nextInt();  
        for(int i = 0; i<10; i++)  
        {  
            if(myarray[i]==key)  
            {  
                location = i+1;  break;  
            }  
            else   
                location = 0;   
        }  
        if(location != 0)  
        {  
            System.out.println("key found at location " + location);  
        }  
        else   
            System.out.println("Key not found");  
    }  
}

Output:

The input array is

21 43 23 54 75 13 5 8 25 10

Enter key

23

key found at location 3

Linear search can be performed on any linear data structure having sorted or unsorted elements. But it takes a longer time if there are too many elements and if the key element is towards the end as each element is compared with the key value.

Binary Search

Binary search is a technique that uses “divide and conquer” technique to search for a key. It works on a sorted linear list of elements. The sorted list is the basic requirement for a binary search to work.

In the binary search method, the list is repeatedly divided into half and the key element is searched in both the halves of the list until the key is found.

For Example, let us take the following sorted array of 10 elements.

Binary Search

Let us say the key = 21 is to be searched in the array.

Let us calculate the middle location of the array.

Mid = 0+9/2 = 4

For Example, let us take the following sorted array of 10 elements.

calculate the middle location

Key = 21

First, we will compare the key value with the [mid] element. We find that the element value at mid = 21.

compare the key value with [mid] element

Thus we find that key = [mid]. Hence the key is found.

key = 25

key = [mid]

We first compare the key value to mid. So (21 < 25), we will directly search for the key in the upper half of the array.

compare the key value to mid

Now again we will find the mid for the upper half of the array.

Mid = 4+9/2 = 6

The value at location [mid] = 25

The value at location [mid] = 25

Now we compare the key element with the mid element. So (25 == 25), thus we have found the key at location [mid].

We repeatedly divide the array and by comparing the key element with the mid, we decide in which half to search for the key.

Given below are the C++ and Java implementation for binary search.

C++ Implementation

#include <iostream>
#include <string>
using namespace std;
int binarySearch(int myarray[], int beg, int end, int key)  
{  
    int mid;  
    if(end >= beg) {     
        mid = (beg + end)/2;  
        if(myarray[mid] == key)  
        {  
            return mid+1;  
        }  
        else if(myarray[mid] < key) {  
            return binarySearch(myarray,mid+1,end,key);  
        }  
        else {  
            return binarySearch(myarray,beg,mid-1,key);  
        }  
    }  
    return -1;   
}   
int main ()  
{  
    int myarray[10] = {5,8,10,13,21,23,25,43,54,75};  
    int key, location=-1;   
    cout<<"The input array is"<<endl;
    for(int i=0;i<10;i++){
        cout<<myarray[i]<<" ";
    }
    cout<<endl;
    cout<<"Enter the key that is to be searched:"; cin>>key;  
    location = binarySearch(myarray, 0, 9, key);  
    if(location != -1)  {  
        cout<<"Key found at location "<<location; 
    }  
    else   {  
        cout<<"Requested key not found";
    }  
}   

Output:

The input array is
5 8 10 13 21 23 25 43 54 75
Enter the key that is to be searched:21
Key found at location 5

Binary Search c++

Java Implementation

import java.util.*;
import java.lang.*;
import java.io.*;
class Main {  
public static void main(String[] args) {  
    int[] myarray = {5,8,10,13,21,23,25,43,54,75};  
    int key, location = -1;  
    System.out.println("The input array is");
    for(int i=0;i<10;i++){ System.out.print(myarray[i]+" "); } System.out.println(); System.out.println("Enter the key to be searched"); Scanner sc = new Scanner(System.in); key = sc.nextInt(); location = binarySearch(myarray,0,9,key); if(location != -1) System.out.println("the location of the key is "+location); else System.out.println("Key not found"); } public static int binarySearch(int[] myarray, int beg, int end, int key) { int mid; if(end >= beg)   
    {     
        mid = (beg + end)/2;  
        if(myarray[mid] == key)  
        {  
            return mid+1;  
        }  
        else if(myarray[mid] < key)   
        {  
            return binarySearch(myarray,mid+1,end,key);  
        }  
        else   
        {  
            return binarySearch(myarray,beg,mid-1,key);  
        }  
      
    }  
    return -1;   
}  
}  

Output:

The input array is

5 8 10 13 21 23 25 43 54 75

Enter the key to be searched

21

the location of the key is 5

Binary search is more efficient in terms of time and correctness. Linear search technique is seldom used as it is more cumbersome and slower. Binary search is a lot faster when compared to a linear search.

Conclusion

The searching techniques help us to search for information stored on a computer so that the user can proceed with the other tasks of information processing. Linear search technique is simple and easier but is not used extensively.

Binary search technique is much faster and efficient hence is used extensively.

In our upcoming tutorial, we will explore the various sorting techniques in detail.

=> Check Out The Perfect C++ Training Guide Here.