In this section of the tutorial, we will discuss Searching in Data Structure, which includes two main techniques of searching, i.e. Linear Search and Binary Search. These Searching Techniques are important in solving Data Structure problems.

Now, let’s move on to the introduction and understand what is Searching in Data Structure.

What is Searching in Data Structure?

Searching is a method of finding the location of a target in a list of objects or data items in an array. We will soon learn different techniques of Searching in Data Structure.

• In every searching algorithm, we start the operation by searching the list and then returning one of two cases, i.e. if the target is found in the list or the target is not found in the list.
• Throughout the tutorial, we will implement different searching algorithms using arrays.
• The searching algorithm can be implemented on both internal and external data structures.
• The efficiency of the searching algorithms in data structure is decided by analyzing how fast the target is found while consuming the least possible memory.
• The searching algorithm is used in solving problems where we need to find an element among a large number of elements.

As we discussed above, there are different types of searching techniques, and two of the most common searching techniques will be discussed further.

Different Searching Techniques

When we want to search an element in a list of data items, there could be two results, search successful and search unsuccessful. There are two most commonly used searching algorithms or techniques in data structure, i.e. Linear Search and Binary Search.

Linear Search

Linear Search is the most basic used in data structures. As the name suggests, the target is searching linearly in the list and it can be implemented on a list that is both sorted and unsorted.

• Linear Search can only be used while searching among a few elements.
• It is not usually used in searching elements more than 16.
• Every element in the list is matched one by one with the target.
• If the target is matched with any element, the search is successful.
• And if the target is not matched with any of the elements, it is understood that the target is not present in the list and hence the search becomes unsuccessful.

Binary Search

Binary Search is comparatively faster than the Linear Search. It is quick in implementation which makes it an efficient searching technique in data structures.

• Binary Search works only on a sorted list.
• The searching begins with comparing the elements from the beginning and end with the middle element in the list.
• If the target is found, then the search is successful.
• Otherwise, the list is divided into halves and again the elements are compared with middle elements of both the halves.
• The algorithm of binary search starts with comparing whether the target element is greater and smaller than the middle element of the list.
• If the target is smaller than the middle element, then the searching will only work on the first half of the list.
• If the target is greater than the middle element, then the searching will only work on the second half of the list.

Advantages of Searching in Data Structure

There are many advantages of Searching algorithms in Data Structures, some of which are discussed below.

• Linear Search technique is useful in handling smaller list items as it provides fast execution due to the speed of simple increment in for each element.
• Linear Search is very basic, resource efficient, and saves a lot of memory.
• Linear Search can be implemented on both sorted and unsorted arrays and linked lists.
• Binary Search technique is useful in handling a large number of items in the list and it is much faster than the Linear Search algorithm.
• It can only be implemented on sorted arrays and linked lists which makes it faster to execute and saves a lot of memory.
• Binary Search technique helps in understanding bigger and complex concepts of data structures like binary search tree and other trees.

Difference between Linear Search and Binary Search

Examples of Searching in Data Structure

Linear Search

Code:

#include<stdio.h>
int main()
{
    int arr[8]={10,12,14,16,2,4,8,6};
    int a,x=0,i;
    printf("Enter a value to search in the array: ");
    scanf("%d",&a);
    for(i=0;i<=8;i++)
    {
        if(a==arr[i])
        {
            x=1;
            break;
        }
        else
        {
           x=0;
        }
    }
    if(x==1)
    printf("Data found at location arr[%d]\n",i);
    else
    printf("Data not found at any location\n"); 
    return 0;
}

Output:

Enter a value to search in the array: 8
Data found at location arr[6]

Binary Search

Code:

#include<stdio.h>
int main()
{
    int arr[12]={10,20,30,40,50,60,70,80,90,100,110,120};
    int i=0,j,k=11;
    int value,check=0;
    printf("Enter a data to search:  ");
    scanf("%d",&value);
    while(i<=k)
    {
        j=(i+k)/2;
        if(arr[j]==value)
        {
            check=1;
            break;
        }
        else
        {
            if(arr[j]<value)
                {
                    i=j+1;                    
                }
            else
                k=j-1;  
        }
    }
    if(check==1)
        printf("Data found\n");
    else
        printf("Data not found\n");
    return 0;
}

Output:

Enter a data to search:  110
Data found

In the next section of the tutorial, we will discuss the Linear Search in Data Structure in detail. It is also known as Sequential Search. The Linear Search is used to locate an item in an array or list. We will understand the concept used in Linear Search to find an item in a list, the algorithm of Linear Search, and also we will implement the Linear Search in code using C and C++ to perform operations.