Question

In C++ what are the searching methods? Please explain and give some examples.

Answer 1

Two search are avalable in C++

• Linear Search or Sequential Search
• Binary Search

What is Linear Search?

This is the simplest method for searching. In this technique of searching, the element to be found in searching the elements to be found is searched sequentially in the list. This method can be performed on a sorted or an unsorted list (usually arrays). In case of a sorted list searching starts from 0^th element and continues until the element is found from the list or the element whose value is greater than (assuming the list is sorted in ascending order), the value being searched is reached.

As against this, searching in case of unsorted list also begins from the 0^th element and continues until the element or the end of the list is reached.

Example:
The list given below is the list of elements in an unsorted array. The array contains ten elements. Suppose the element to be searched is '46', so 46 is compared with all the elements starting from the 0^th element, and the searching process ends where 46 is found, or the list ends.

The performance of the linear search can be measured by counting the comparisons done to find out an element. The number of comparison is 0(n).

Algorithm for Linear Search

It is a simple algorithm that searches for a specific item inside a list. It operates looping on each element O(n) unless and until a match occurs or the end of the array is reached.

• algorithm Seqnl_Search(list, item)
• Pre: list != ;
• Post: return the index of the item if found, otherwise: 1
• index <- fi
• while index < list.Cnt and list[index] != item //cnt: counter variable
• index <- index + 1
• end while
• if index < list.Cnt and list[index] = item
• return index
• end if
• return: 1
• end Seqnl_Search

• Features of Linear Search Algorithm

• It is used for unsorted and unordered small list of elements.
• It has a time complexity of O(n), which means the time is linearly dependent on the number of elements, which is not bad, but not that good too.
• It has a very simple implementation.

Program :

#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";  
    }  
   
}

What is Binary Search?

Binary search is a very fast and efficient searching technique. It requires the list to be in sorted order. In this method, to search an element you can compare it with the present element at the center of the list. If it matches, then the search is successful otherwise the list is divided into two halves: one from the 0^th element to the middle element which is the center element (first half) another from the center element to the last element (which is the 2^nd half) where all values are greater than the center element.

The searching mechanism proceeds from either of the two halves depending upon whether the target element is greater or smaller than the central element. If the element is smaller than the central element, then searching is done in the first half, otherwise searching is done in the second half.

Features of Binary Search

1. It is great to search through large sorted arrays.
2. It has a time complexity of O(log n) which is a very good time complexity. We will discuss this in details in the Binary Search tutorial.
3. It has a simple implementation.

Algorithm for Binary Search

• algorithm Binary_Search(list, item)
• Set L to 0 and R to n: 1
• if L > R, then Binary_Search terminates as unsuccessful
• else
• Set m (the position in the mid element) to the floor of (L + R) / 2
• if Am < T, set L to m + 1 and go to step 3
• if Am > T, set R to m: 1 and go to step 3
• Now, Am = T,
• the search is done; return (m)

#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";
    }  
}