What Is Searching And How To Use Of 3 Types

SEARCHING

One of the most common and time consuming part in computer science is searching. It is a process for finding location of target among a list of objects.

The two common ways of searching are sequential search and binary search. In this blog, you will learn about different types of sequential search. 

What are the use of sequential or linear search? 

Sequential search or linear search is used to find an element in both sorted as well as unsorted arrays and lists. It is preferred only for small lists(usually a list with less than 16 elements) because the time complexity of Sequential search increases with increase in number of elements and is equal to O(n) in the worst case situation.

Simple Sequential search:

How does simple sequential search works?

We compare the element at each index with the target element until the target element is found or until we reach the end of the array.

#include<stdbool.h>
#include<stdio.h>
bool search(int numList[], int *locn, int target, int last);
int main()
{
    int numList[] = {1, 7, 8, 9, 132, -76, 990, 0, -930};
    int last, target, locn;
    last = sizeof(numList) / sizeof(int) - 1; //index of last element
    bool found;
    printf("Enter a number:\n");
    scanf("%d", &target);
    found = search(numList, &locn, target, last);
    if (found)
    {
        printf("Location: %d", locn);
        return 0;
    }
    printf("Not found");
    return 0;
}

bool search(int numList[], int *locn, int target, int last)
{
    int looker;
    looker = 0;
    while (looker < last && target != numList[looker])
        looker++;
    *locn = looker;
    if (target == numList[looker])
        return true;
    return false;
}

There are three types of sequential searches:

• Sentinel search

• Probability search

• Ordered list search

Sentinel Search:     

Sentinel means an indicator.

In this search we will reduce the condition of loop by adding an extra sentinel element at the end of the list.
we will loop through the list until we find the target element.

#include <stdbool.h>
#include <stdio.h>
bool sentinelSearch(int numList[], int *locn, int target, int last);
int main()
{
    int numList[] = {1, 7, 8, 9, 132, -76, 990, 0, -930};
    int last, target, locn;
    last = sizeof(numList) / sizeof(int) - 1; //index of last element

    bool found;
    printf("Enter a number:\n");
    scanf("%d", &target);
    numList[last + 1] = target;
    found = sentinelSearch(numList, &locn, target, last);
    if (found)
    {

        printf("Location: %d", locn);
        return 0;
    }
    printf("Not found");

    return 0;
}

bool sentinelSearch(int numList[], int *locn, int target, int last)
{
    int looker;
    looker = 0;
    while (target != numList[looker])
    {
        looker++;
    }
    *locn = looker;

    if (*locn <= last)
        return true;
    return false;
}

Probability search: 

It is one of more useful variation of searching. In this searching, we put the most probability elements at the beginning and least probable elements at the of the list.
we loop through the list until the element is found or until we reach the end of the array and when the element is found we exchange it with the element before it.

#include <stdbool.h>
#include <stdio.h>
bool probabilitySearch(int numList[], int *locn, int target, int last);
int main()
{
    int numList[] = {1, 7, 8, 9, 132, -76, 990, 0, -930};
    int last, target, locn;
    last = sizeof(numList) / sizeof(int) - 1; //index of last element
    bool found;
    printf("Enter a number:\t");
    scanf("%d", &target);
    found = probabilitySearch(numList, &locn, target, last);
    printf("value of element in location before swap:%d", numList[locn]);
    printf("\nvalue of element in location after swap:%d", numList[locn - 1]);

    if (found)
    {
        printf("\nLocation of element after swap: %d", locn);
        return 0;
    }
    printf("Not found");

    return 0;
}

 bool probabilitySearch(int numList[], int *locn, int target, int last)
  {
    int looker;
    looker = 0;
    while (looker < last && target != numList[looker])
    {
        looker++;
    }
    *locn = looker;
    //swaping of values after finding value to before index
    if (target == numList[looker])
    {
        int temp = numList[looker - 1];
        numList[looker - 1] = numList[looker];
        numList[looker] = temp;

        return true;
    }
    return false;
}

Ordered list search: 

It is commonly used in linked list search. In this searching, we need not search till the end of the list to determine the target is not in the list.
we loop through the list until the element is less than or equal to the target element provided it is sorted in ascending order. 

we loop through the list until the element is less than or equal to the target element provided it is sorted in ascending order. 

#include <stdbool.h>
#include <stdio.h>
//prototype
bool orderedlistSearch(int numList[], int *locn, int target, int last);
//main function decleration
int main()
{
    //the array values or the values in the list has to be in an ordered way i.e ascending or  
    //descending order otherwise the search wont work
    int numList[] = {1, 7, 8, 9, 132, 990};
    int last, target, locn;
    last = sizeof(numList) / sizeof(int) - 1; //index of last element
    bool found;
    printf("Enter a number:\t");
    scanf("%d", &target);
    found = orderedlistSearch(numList, &locn, target, last);
    if (found)
    {
        printf("Found at Location: %d", locn);
        return 0;
    }
    printf("Not found");

    return 0;
}

 bool orderedlistSearch(int numList[], int *locn, int target, int last)
    {
        int looker;
        if (target < numList[last])
        {
            looker = 0;
            while (target > numList[looker])
            {
                looker += 1;
            }
        }
        else
        {
            looker = last;
        }
        *locn = looker;
        if (target == numList[looker])
            return true;
        return false;
    }