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.
What You Will Learn:
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.
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.
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.
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](https://www.softwaretestinghelp.com/wp-content/qa/uploads/2019/06/compare-the-key-value-with-mid-element.png)
Thus we find that key = [mid]. Hence the key is found.
key = 25
![key = [mid]](https://www.softwaretestinghelp.com/wp-content/qa/uploads/2019/06/key-mid.png)
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.
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](https://www.softwaretestinghelp.com/wp-content/qa/uploads/2019/06/The-value-at-location-mid-25.png)
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
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.