Search In Data Structure, Linear, Binary, Explanation, Code, Algorithm

October 16, 2020February 21, 2022 CS Electrical And Electronics

Hello guys, welcome back to my blog. In this article, I will discuss search in data structure, types of searching algorithms, what is linear search, binary search, interpolation search, jump search, Code for linear search & binary search, etc.

If you need an article on some other topics then comment us below in the comment box. You can also catch me @ Instagram – Chetan Shidling.

Also, read:

Search In Data Structure

Searching means to determine whether a special value is now in an array or not. If the value is now in the array, then searching is assumed to be successful and the searching method gives the place of that value in the array. But, if the content is not being in the array, the searching method displays a relevant message and in this case, searching is assumed to be unsuccessful.

The different methods of searching are:

Linear search
Binary search
Interpolation search
Jump search

01. Linear search

Linear search, too pronounced as sequential search, is a really simple process used for searching an array for an appropriate value. It operates by comparing the value to be searched with each component of the array one by one in a series until a match is found. Linear search is often utilized to search an unordered arrangement of elements.

Program to perform linear search in data structure and algorithm?

#include <stdio.h>
#include <stdlib.h>
int linearSearch(int arr[], int size, int element){
    int i;
    for(i =0; i < size; i++)
    {
        if(arr[i]==element){
            return i;
        }
    }

    return 0;

}
int main()
{
    int arr[] = {1, 3, 34, 44, 555, 234 , 45, 123, 524, 22};
    int size = sizeof(arr)/sizeof(int);
    int element = 0;
    printf("Enter the element to be search\n");
    scanf("%d", & element);
    int searchIndex = linearSearch(arr, size, element);
    if(searchIndex!=0)
        printf("The element %d was found at index %d \n", element, searchIndex);
    else
        printf("Element is not present, search other element");
    return 0;

}

Output:

Enter the element to be search
44
The element 44 was found at index 3

Enter the element to be search
2342
Element is not present, search other element

02. Binary search

A binary search is a searching algorithm that operates efficiently by a sorted list. Binary search breaks the list in two equal halves. When we are searching for a special word meaning in a directory, we initial open the directory from the middle and later decide whether to look for the name in the front part of the directory or in the other part of the directory. Again, we open any pages in the middle and the whole method is repeated until we finally find the right name.

The above image clearly says the working of binary search. Binary search is performed on sorted lists, first, we will find the middle value, then we will see the value is at the right or left side. In the above image, the value is on the right side, so we will make the middle value as low and again start finding the middle value, this process goes on until the value is found.

Program to perform binary search in data structure and algorithm?

#include <stdio.h>
#include <stdlib.h>
int binarySearch(int arr[], int size, int element){
    int mid, high, low;
    low = 0;
    high = size-1;
    //start searching
    while(low<=high){
        mid = (low + high)/2;
        if (arr[mid] == element){
            return mid;
        }
        if(arr[mid]<element){
            low = mid+1;
        }
        else{
            high = mid-1;
        }
    }
    return 0;
}

int main()
{
    int arr[] = {1, 3, 4, 44, 55, 134 , 245, 323, 524, 622};
    int size = sizeof(arr)/sizeof(int);
    int element = 0;
    printf("Enter the element to be search\n");
    scanf("%d", & element);
    int searchIndex = binarySearch(arr, size, element);
    if(searchIndex!=0)
        printf("The element %d was found at index %d \n", element, searchIndex);
    else
        printf("Element is not present, search other element");
    return 0;
}

Output:

Enter the element to be search
44
The element 44 was found at index 3

Enter the element to be search
200
Element is not present, search other element

03. Interpolation search

Interpolation search, also recognized as an extrapolation search, is a searching method that obtains a particularized value in a sorted array. The idea of interpolation search is related to how we search for word meaning in a dictionary book by which a work’s entries are ordered. Suppose you are searching word meaning in dictionary example Chetan, you start the search from a word which starts from c in order ways.

04. Jump search

If we have a previously sorted list, then the additional suitable algorithm to search for value is jump search or also called a block search. In the jump search, it is not required to scan all the elements in the list to obtain the desired value. We only check an element and if it is shorter than the desired value, then any of the elements following it are skipped by jumping forward. After going a little forward again, the element is checked.

I hope this article may help you all a lot. Thank you for reading. If you have any doubts related to this article “Search in data structure”, then comment below in the comment box.

Also, read: