Searching Algorithms in Data Structure

Searching is a process of retriving or locating or finding information matching with some specific value.

In data structure there are two types of searching.

  • Linear or sequencial search
  • Binary search

 Linear or Sequencial Search

It is a simplest form of searching and can be applied for sequencial storage such as array, stack, queue, linked list.
Algorithm
Linear/Sequencial Search

Step 1: Start
Step 2: Set 0 to i
Step 3: Read and store value to search in val
Step 4: if a(i) = val, print value is found at (i+1) position and go to step 8   
Step 5: Set i to i + 1
Step 6: If i is less than n then, go to Step 4
Step 7: Print element not found
Step 8: Stop

n - size of array
a - array
val - value to be searched in array

Source Code
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

int main()
{

    int n;
    printf("Enter the size of array : ");
    scanf("%d", &n);

    int arr[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    int val;
    printf("Enter the value to search : ");
    scanf("%d", &val);

    for (int i = 0; i < n; i++)
    {
        if (arr[i] == val)
        {
            printf("%d found at %dth position.", val, i + 1);
            exit(0);
        }
    }
    printf("%d is not found.", val);
    return 0;
}

Output

Enter the size of array : 5
6 3 8 5 2
Enter the value to search : 5
5 found at 4th position.

Enter the size of array : 5
6 3 8 5 2
Enter the value to search : 1
1 is not found.

Advantages
  • Simple searching method.
  • Searching can be applied on any type of data (sorted/unsorted).
  • No additional data structure is required.
Disadvantages
  • If total numbers are large, then it is inefficient.
  • It is a time consuming process. 

 

Binary Search

It is the fastest searching method can be applied only when data is in sorted order.
If data is in sorted order, the value to search is divided into two parts -
1] Middle to left to search less value.
2] Middle to right to search greater value.
Algorithm
Binary Search

Step 1: Start
Step 2: Set 0 to i
Step 3: Read and store value to search in val
Step 4: Set 0 to low
Step 5: Set n-1 to high
Step 6: If low > high go to step 11
Step 7: Set mid = (low + high) / 2
Step 8: If val < a[mid] then, set high = mid - 1 & go to step 6
Step 9: If val > a[mid] then, set low= mid + 1 & go to step 6
Step 10:If val == a[mid]
        print value is present at mid+1 position and go to 12
Step 11:print value is absent
Step 12:Stop

n - size of array
a - array
val - value to be searched in array

Source Code
#include <stdio.h>
#include <conio.h>
#include <stdlib.h>

int main()
{

    int n;
    printf("Enter the size of array : ");
    scanf("%d", &n);

    int arr[n];
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &arr[i]);
    }

    int val;
    printf("Enter the value to search : ");
    scanf("%d", &val);

    int low, high, mid;
    low = 0;
    high = n - 1;
    while (low <= high)
    {
        mid = (low + high) / 2;
        if (arr[mid] == val)
        {
            printf("%d is present at %dth position.", val, mid+1);
            exit(0);
        }
        else if (arr[mid] <= val)
        {
            low = mid + 1;
        }
        else
        {
            high = mid - 1;
        }
    }

    printf("%d not found.", val);
    return 0;
}

Output

Enter the size of array : 5
23 45 56 78 90
Enter the value to search : 45
45 is present at 2th position.

Enter the size of array : 5
23 45 56 78 90
Enter the value to search : 91
91 not found.

Advantages
  • It is a fastest searching method because it searches the value into two parts.
Disadvantages
  • It can be applied only when data is in sorted order.

Comments

Post a Comment

Popular posts from this blog

Sorting Algorithms in Data Structure

Sorting is a process of arranging information either in ascending or in descending order of key values. In data structures there are techniques available to sort the data. Types of sorting algorithms Bubble sort Insertion sort Selection sort Quick sort Radix sort Merge sort   1. Bubble Sort It is one of the simplest & popular sorting method. The basic idea of this sorting is that in each pass we have to compare a successive pair of element i.e. a[i] & a[i+1]. Interchange these two values, if they are not place in proper order. Place the element in it's correct position in each pass. In first pass largest element is shifted at bottom. In second pass second largest will be shifted to the second last position & so on. Thus to sort n values n-1 passes are required. Algorithm Bubble Sort Step 1: Start Step 2: Set 1 to pass Step 3: Set o to i Step 4: if a[i]> a[i+1] then, Swap a[i] & a[i+1] Step 5: Add I to i. Step 6: If i...
Read more

Circular Linked List

Image
I n a Circular Linked List the first and the last elements are adjacent. A linked list can be made circular by storing the address of the first node in the next field of the last node. In a circular linked list, last node is connected back to the first node. In some applications, it is convenient to use circular linked list. A queue data structure can be implemented using a circular linked list, with a single pointer "rear" as the front node can be accessed through the rear node. Implementation of Circular Linked List Circular Linked List Creation and Traversal Algorithm for traversing a circular list is slightly different than the same algorithm for a singly linked list because "NULL" is not encountered. Source Code (Circular Linked List Creation and Traversal) #include <stdio.h> #include <stdlib.h> struct Node { int data; struct Node *next; }; void CircularLinkedListTraversal(stru...
Read more