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

Page Contents

## 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

### 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.

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={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, 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;
}```

### 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

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

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:-

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:-

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:-

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={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.
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;
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)