Home » Data Structure

Searching - Linear/ Sequential, Binary and Interpolation Tutorial

Searching (Linear/ Sequential, Binary and Interpolation Searching) Data Structure Tutorial with C & C++ Programming: This section provides a brief description about DATA Structure – Searching, contains Linear Searching/ Sequential Searching, Binary Searching and Interpolation Searching with Examples and their features.
Submitted by IncludeHelp, on June 18, 2020

Data Structure Searching

Searching is the process of finding an element in a given list. In this process, we check items that are available in the given list or not.

Type of searching

1. Internal Search: In this search, searching is performed on main or primary memory.
2. External Search: In this search, searching is performed in secondary memory.

Complexity Analysis

Complexity analysis is used to determine, the algorithm will take the number of resources (such as time and space) necessary to execute it.

There are two types of complexities: 1) Time Complexity and 2) Space Complexity.

Searching Techniques

There are three types of searching techniques,

1. Linear or sequential search
2. Binary search
3. Interpolation search

A) Linear/ Sequential Search

Linear/Sequential searching is a searching technique to find an item from a list until the particular item not found or list not reached at the end. We start the searching from 0^th index to N^th-1 index in a sequential manner, if a particular item found, returns the position of that item otherwise return failure status or -1.

Algorithm:

LINEAR_SEARCH (LIST, N, ITEM, LOC, POS)
In this algorithm, LIST is a linear array with N elements, 
and ITEM is a given item to be searched. This algorithm finds 
the location LOC of ITEM into POS in LIST, or sets POS := 0, 
if search is unsuccessfull.
1.	Set POS  :=  0;
2.	Set LOC  :=  1;
3.	Repeat STEPS a and b while LOC <= N
    a.	If ( LIST[LOC] = ITEM) then 
        i.	SET POS := LOC;  [get position of item]
        ii.	return;
    b.	Otherwise
        i.	SET LOC := LOC + 1 ; [increment counter]
4.	[END OF LOOP]
5.	return 

Complexity of Linear search:

The complexity of the search algorithm is based on the number of comparisons C, between ITEM and LIST [LOC]. We seek C (n) for the worst and average case, where n is the size of the list.

Worst Case: The worst case occurs when ITEM is present at the last location of the list, or it is not there at al. In either situation, we have, C (n) = n

Now, C (n) = n is the worst-case complexity of linear or sequential search algorithm.

Average case: In this case, we assume that ITEM is there in the list, and it can be present at any position in the list. Accordingly, the number of comparisons can be any of the numbers 1, 2, 3, 4, ..., n. and each number occurs with probability p = 1/n. Then,
C (n) = n/2

Implementation of Linear/ Sequential Search

• Using C
• Using C++

#include <stdio.h>
#define SIZE 5

/*Function to search item from list*/
int LinearSearch(int ele[], int item)
{
    int POS = -1;
    int LOC = 0;

    for (LOC = 0; LOC < SIZE; LOC++) {
        if (ele[LOC] == item) {
            POS = LOC;
            break;
        }
    }

    return POS;
}

int main()
{
    int ele[SIZE];
    int i = 0;
    int item;
    int pos;

    printf("\nEnter Items : \n");

    for (i = 0; i < SIZE; i++) {
        printf("Enter ELE[%d] : ", i + 1);
        scanf("%d", &ele[i]);
    }

    printf("\n\nEnter Item To Be Searched : ");
    scanf("%d", &item);

    pos = LinearSearch(ele, item);

    if (pos >= 0) {
        printf("\nItem Found At Position : %d\n", pos + 1);
    }
    else {
        printf("\nItem Not Found In The List\n");
    }

    return 0;
}

    First run:

    Enter Items : 
    Enter ELE[1] : 20
    Enter ELE[2] : 10
    Enter ELE[3] : 30
    Enter ELE[4] : 40
    Enter ELE[5] : 50


    Enter Item To Be Searched : 30

    Item Found At Position : 3

    Second run:

    Enter Items : 
    Enter ELE[1] : 20
    Enter ELE[2] : 10
    Enter ELE[3] : 30
    Enter ELE[4] : 40
    Enter ELE[5] : 50


    Enter Item To Be Searched : 24

    Item Not Found In The List

#include <iostream>

using namespace std;
#define SIZE 5

class Search {
private:
    int ele[SIZE];

public:
    void Input();
    int LinearSearch(int item);
};

//Input Element into the list
void Search::Input()
{
    int i = 0;

    cout << "\nEnter Items : \n";

    for (i = 0; i < SIZE; i++) {
        cout << "Enter ELE[" << i + 1 << "] : ";
        cin >> ele[i];
    }
}

//Function to search item from list
int Search::LinearSearch(int item)
{
    int POS = -1;
    int LOC = 0;

    for (LOC = 0; LOC < SIZE; LOC++) {
        if (ele[LOC] == item) {
            POS = LOC;
            break;
        }
    }

    return POS;
}

int main()
{
    int i = 0;
    int item;
    int pos;

    Search s = Search();

    s.Input();

    cout << "\n\nEnter Item To Be Searched : ";
    cin >> item;

    pos = s.LinearSearch(item);

    if (pos >= 0) {
        cout << "\nItem Found At Position : " << pos + 1 << endl;
    }
    else {
        cout << "\nItem Not Found In The List\n";
    }

    return 0;
}

    First run:

    Enter Items : 
    Enter ELE[1] : 20
    Enter ELE[2] : 10
    Enter ELE[3] : 30
    Enter ELE[4] : 40
    Enter ELE[5] : 50


    Enter Item To Be Searched : 30

    Item Found At Position : 3

    Second run:

    Enter Items : 
    Enter ELE[1] : 20
    Enter ELE[2] : 10
    Enter ELE[3] : 30
    Enter ELE[4] : 40
    Enter ELE[5] : 50


    Enter Item To Be Searched : 24

    Item Not Found In The List

B) Binary Search

It is a special type of search work on a sorted list only. During each stage of our procedure, our search for ITEM is reduced to a restricted segment of elements in LIST array. The segment starts from index LOW and spans to HIGH.

LIST [LOW], LIST [LOW+1], LIST [LOW+2], LIST [LOW+ 3]….. LIST[HIGH]

The ITEM to be searched is compared with the middle element LIST[MID] of segment, where MID obtained as,

MID = ( LOW + HIGH )/2

We assume that the LIST is sorted in ascending order. There may be three results of this comparison,

1. If ITEM = LIST[MID], the search is successful. The location of the ITEM is LOC := MID.
2. If ITEM < LIST[MID], the ITEM can appear only in the first half of the list. So, the segment is restricted by modifying HIGH = MID - 1.
3. If ITEM > LIST[MID], the ITEM can appear only in the second half of the list. So, the segment is restricted by modifying LOW = MID + 1.

Initially, LOW is the start index of the array, and HIGH is the last index of the array. The comparison goes on. With each comparison, low and high approaches near to each other. The loop will continue till LOW < HIGH.

Algorithm

Let the item to be searched is: 15
Step1: Initially
    1.	List[low]  = list[0] = 12
    2.	List[high] = list[9] = 99
    3.	Mid= (low + high)/2 = (0+9)/2 = 4
    4.	List[mid]=  list[4] = 35
Step2: Since item (15) < list [mid] (35); high = mid -1 = 3
    1.	List[low]  = list[0] = 12
    2.	List[high] = list[3] = 28
    3.	Mid =(low + high)/2 = (0+3)/2 = 1
    4.	List [mid] = list [1] = 15.
Step3: Since item (15) = list [mid] (15); 
It is success, the location 1 is returned. 

BINARY SEARCH (LIST, N, ITEM, LOC, LOW, MID, HIGH)
Here LIST is a sorted array with size N, ITEM is the given information. 
The variable LOW, HIGH and MID denote, respectively,
the beginning, end and the middle of segment of LIST. 
The algorithm is used to find the location LOC of ITEM in LIST array. 
If ITEM not there LOC is NULL.

1.	Set LOW := 1; LOW := N;
2.	Repeat step a  to d while LOW <= HIGH and ITEM != LIST(MID)
    a.	Set MID := (LOW + HIGH)/2
    b.	If ITEM = LIST(MID), then
        i.	Set LOC := MID
        ii.	Return
    c.	If ITEM < LIST(MID) then
        i.	Set HIGH := MID - 1;
    d.	Otherwise
        i.	Set LOW := MID + 1;
3.	SET  LOC := NULL
4.	return

Complexity of Binary search

The complexity measured by the number f(n) of comparisons to locate ITEM in LIST where LIST contains n elements. Each comparison reduces the segment size in half.

Hence, we require at most f(n) comparisons to locate ITEM, where, 2^c >= n

Approximately, the time complexity is equal to log₂n. It is much less than the time complexity of a linear search.

Implementation of Binary Search

• Using C
• Using C++

#include <stdio.h>
#define SIZE 5

/*To search item from sorted list*/
int BinarySearch(int ele[], int item)
{
    int POS = -1;
    int LOW = 0;
    int HIGH = SIZE;
    int MID = 0;

    while (LOW <= HIGH) {
        MID = (LOW + HIGH) / 2;

        if (ele[MID] == item) {
            POS = MID;
            break;
        }
        else if (item > ele[MID]) {
            LOW = MID + 1;
        }
        else {
            HIGH = MID - 1;
        }
    }

    return POS;
}

int main()
{
    int ele[SIZE];
    int i = 0;
    int item;
    int pos;

    printf("\nEnter Items : \n");

    for (i = 0; i < SIZE; i++) {
        printf("Enter ELE[%d] : ", i + 1);
        scanf("%d", &ele[i]);
    }

    printf("\n\nEnter Item To Be Searched : ");
    scanf("%d", &item);

    pos = BinarySearch(ele, item);

    if (pos >= 0) {
        printf("\nItem Found At Position : %d\n", pos + 1);
    }
    else {
        printf("\nItem Not Found In The List\n");
    }

    return 0;
}

    First run:

    Enter Items : 
    Enter ELE[1] : 10
    Enter ELE[2] : 20
    Enter ELE[3] : 30
    Enter ELE[4] : 40
    Enter ELE[5] : 50


    Enter Item To Be Searched : 30

    Item Found At Position : 3

    Second run:

    Enter Items : 
    Enter ELE[1] : 10
    Enter ELE[2] : 20
    Enter ELE[3] : 30
    Enter ELE[4] : 40
    Enter ELE[5] : 50


    Enter Item To Be Searched : 24

    Item Not Found In The List

#include <iostream>

using namespace std;
#define SIZE 5

class Search {
private:
    int ele[SIZE];

public:
    void Input();
    int BinarySearch(int item);
};

//Input Element into the list
void Search::Input()
{
    int i = 0;

    cout << "\nEnter Items : \n";

    for (i = 0; i < SIZE; i++) {
        cout << "Enter ELE[" << i + 1 << "] : ";
        cin >> ele[i];
    }
}

//To search item from sorted list
int Search::BinarySearch(int item)
{
    int POS = -1;
    int LOW = 0;
    int HIGH = SIZE;
    int MID = 0;

    while (LOW <= HIGH) {
        MID = (LOW + HIGH) / 2;

        if (ele[MID] == item) {
            POS = MID;
            break;
        }
        else if (item > ele[MID]) {
            LOW = MID + 1;
        }
        else {
            HIGH = MID - 1;
        }
    }

    return POS;
}

int main()
{
    int i = 0;
    int item;
    int pos;

    Search s = Search();

    s.Input();

    cout << "\n\nEnter Item To Be Searched : ";
    cin >> item;

    pos = s.BinarySearch(item);

    if (pos >= 0) {
        cout << "\nItem Found At Position : " << pos + 1 << endl;
    }
    else {
        cout << "\nItem Not Found In The List\n";
    }

    return 0;
}

    First run:

    Enter Items : 
    Enter ELE[1] : 10
    Enter ELE[2] : 20
    Enter ELE[3] : 30
    Enter ELE[4] : 40
    Enter ELE[5] : 50


    Enter Item To Be Searched : 30

    Item Found At Position : 3

    Second run:

    Enter Items : 
    Enter ELE[1] : 10
    Enter ELE[2] : 20
    Enter ELE[3] : 30
    Enter ELE[4] : 40
    Enter ELE[5] : 50


    Enter Item To Be Searched : 24

    Item Not Found In The List

Difference between Linear Search and Binary Search

C) Interpolation Search

This technique is used if the items to be searched are uniformly distributed between the first and the last location. This technique is a simple modification in the binary search when MID is calculated.

Mid = low + (high – low) * ((item – LIST[low])  / (LIST[high] – LIST[low]));

Advantages

1. If the items are uniformly distributed, the average case time complexity is log₂(log₂(n)).
2. It is considered an improvement in binary search.

Disadvantages

1. The calculation of mid is complicated. It increases the execution time.
2. If the items are not uniformly distributed, the interpolation search will have very poor behavior.