Searching techniques in data structures are the algorithms which are designed to process and find element among a list of the elements.

What is Searching?

Definition of Searching in Data structure: The searching in Data structure is a process of finding an element in a data set of data. Searching Techniques are also known as Searching algorithms. There are huge data available (stored) and for finding data we required some technique so that we can access fast as possible within a minimum effort.
What are the types of searching in Data structures?
There are two ways for searching algorithms in Date structures these are as follows

Types of Searching Algorithms

  1. Linear search
  2. Binary search

Let’s start with studying different Searching Technique in Data Structures.

Searching in Data structures
Searching in Data structures

Linear search

Linear search is a simple type of searching in Data structures where we find the element from the set of an element from beginning to end.
What is a Linear Search? : The linear search is a sequential searching for finding value in a list.
Linear search process: In this, we (check) find the element from starting element and continues to check until the finding element to be found within a list and this process done till the last and if there is no such element then there is no element found in a list.

Linear search example

Consider, the following set of elements having the 5 elements stored in an array and find element 20.

Linear Search
Linear Search in Data structure

Similarly, try to find an element which is not available in an array. Find 120 in an array. Follow the same process given above.
10 ≠ 120, 40 ≠ 120 , 20 ≠ 120 , 30 ≠ 120 , 50 ≠ 120
At this point, we reached the end of an array and no match of an element we found in an array. Therefore, there is a no finding element available in an array.
In this way we perform linear searching of data now we write an algorithm for linear searching.

Linear search complexity

The time complexity for linear search is log(N2).

Linear search algorithm

  1. Define an array a[5]={10,20,30,40,50}
  2. Take key input, find=30
  3. Traverse the array
  4. if key==array element then print element found and stop traversing.
  5. else move to next array element
  6. Array reached end
  7. Stop

Linear search program in c

#include <stdio.h>
int main()
{
  int array[100], search, c, n;
  printf("Enter the number of elements in array\n");
  scanf("%d", &n);
  printf("Enter %d integer(s)\n", n);
    for (c = 0; c < n; c++)
      scanf("%d", &array[c]);
  printf("Enter a number to search\n");
  scanf("%d", &search);
  for (c = 0; c < n; c++)
  {
    if (array[c] == search)    /* If required element is found */
    {
      printf("%d is present at location %d.\n", search, c+1);
      break;
    }
  }
  if (c == n)
  printf("%d isn't present in the array.\n", search);
  return 0;
}

Output :

Linear Search algorithm
Linear Searching in Data structure

Binary search

This is another method for finding an element in an array.
What is the binary search? : Binary search is a very fast and efficient searching technique. The condition for binary search is that all elements must be sorted we compare the element with the middle element of the array if it is less than a middle element then we search in a left portion of an array and if it is greater than the middle element then we search in the right portion of an array.
Now we will take that the portion only for a search and compare with the middle element of that portion.
This process will be in iteration up till we find the element or a middle element that has no left or right portion to search.

Binary search example

Consider, the following set of elements and the element searching is 49

Binary Search
Binary Search

Iteration 1:-
Start=0 , end=9 , mid=start+end/2 (0+9/2=4)

Binary seqarch
Binary search

Now the element at a position 4 is 25 compare this with 49 that is 49>25.
The middle element is smaller than finding the element, therefore, our finding element is present in the right position of an array so set start to mid+1.
start= mid+1
=> start= 4+1
so start= 5
Iteration 2:-

Binary Search
Binary Search

Now, Start = 5 and end = 9
Find, mid= 5+9/2 =7
But, 49<57
In this case, finding an element is less than mid-value, so we will find in the left portion.
end = mid-1
= 7-1
= 6
Iteration 3:-

Binary search
Binary search

Start = 5 and end = 6
Find, mid= 5+6/2 = 5
But, 49>30
In this finding, the element is greater than the middle element so we will find in the right portion.
Start = mid+1
= 5+1
= 6
Iteration 4:-

Binary Search
Binary Search

Start = 6 and end = 6
mid= 6+6/2 = 6
6th is the position of 49 and it is mid value, We found the element 49 at 6 position in array.
Mid=49 & Search element=49
In this way we can perform a binary search now we will see the algorithm for Binary search.

Binary search complexity

The time and space complexity for Binary search algorithm.
Worst Complexity: O(log n)
Average Complexity: O(log n)
Best Complexity: O(1)

Binary search algorithm

  1. Take a number of Array element user want. N=5
  2. Take the array elements from a user in ascending order only. a[5]={1,2,3,4,5}
  3. Set start = 0 and end= last element of an array.
  4. Take a finding element from a user. find=4
  5. Then calculate a mid = (Start+end/2)
  6. Compare mid with finding value. 
  7. If mid < find then set start to mid+1.
  8. else set end = mid -1.
  9. calculate Mid and continue with step 6 until one mid-value left (there is no left or right portion left)
  10. If mid == find then print number found.
  11. If start > end print number not found.
  12. Stop.

Now let’s see the Binary search program in a data structure.

Binary search program in c

#include <stdio.h>
int main()
{
  int c, first, last, middle, n, search, array[100];
  printf("Enter number of elements\n");
  scanf("%d",&n);
  printf("Enter %d integers\n", n);
  for (c = 0; c < n; c++)
    scanf("%d",&array[c]);
  printf("Enter value to find\n");
  scanf("%d", &search);
  first = 0;
  last = n - 1;
  middle = (first+last)/2;
  while (first <= last) 
  {
    if (array[middle] < search)
    first = middle + 1;
    else if (array[middle] == search)
    {
      printf("%d found at location %d.\n", search, middle+1);
      break;
    }
    else
      last = middle - 1;
      middle = (first + last)/2; 
   }
  if (first > last)
    printf("Not found! %d isn't present in the list.\n", search);
return 0;
}

Output:-

Binary Search algorithm
Binary Search algorithm

Write A Comment