Searching in Data Structures: In this tutorial, we will study different **Searching Technique in Data Structures**.

**Searching Definition**

- The searching is a process of finding an element in a data set of data.
- 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.

There are two ways for searching these are as follows (**Searching Technique in Data Structures**)

**1. Linear searching**

**2. Binary searching**

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

## Linear search

- Linear search is a simple type of searching where we find the element from the set of an element from beginning to end.
- The linear search is a sequential searching for finding value in a list.
- 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 10 elements stored in an array in a linear way.

Now, find the element **50** in a list so for this we will start checking 50 in the array from start.

It will compare 50 with an element in a first position that is **10 ≠ 50.**

It’s not matching we will move to the next **20 ≠ 50,** again we will move to the next **30 ≠ 50,** again we will move to the next **40 ≠ 50, **again we will move to the next **50 = 50** now the element will match with the finding element that is we found the element in a list now we print the output, We found element 50 in an array.

In this way find **120** in an array. Follow the same process given above.

**10 ≠ 120** , **20 ≠ 120** , **30 ≠ 120** , **40 ≠ 120** , **50 ≠ 120**

**60 ≠ 120**, **70 ≠ 120**, **80 ≠ 120** ,**90 ≠ 120 , 100 ≠ 120**

At this point, we reached the end of an array and no match of an element we finding in 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(N^{2}).

## Linear search algorithm

- Define an array of an element.
- Take input from a user which want to search.
- If both are matching that is array element and the finding element then print
**found**and terminate the function else move to the next element. - If the last element reached then no element in an array found then print
**not found.**

## Linear search program in c

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
#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 of program **

## Binary search

- This is another method for finding an element in an array.
- The condition for binary search is that all elements should 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 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 an iteration up till we find the element or a middle element that has no left or right portion to search.

## Binary search example

Suppose, 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 element therefore our finding element is present in a right position of a array **so set start to mid+1.**

**start= mid+1**

**=> start= 4+1**

**so start= 5**

**Iteration 2:-**

In this, **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 element is greater than middle element so we will find in 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.

In this way we can perform a binary search now we will see the algorithm for Binary search.

## Binary search complexity

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

## Binary search algorithm

- Take a number of Array element user want.
- Next, Take the array elements from a user in ascending order only.
- Take a finding element from a user.
- Set start = 0 and end= last element of an array.
- Then calculate a mid value = (Start+end/2)
- Compare mid value with finding value.
- Check mid value less than finding value if
**yes**set**start to mid+1.**If not, Then set**end = mid -1.** - Mid values and continue with step 6 until one mid value left (there is no left or right portion left)
- If that one mid value is equal to finding element print
**number found.** - If start > end print
**number not found.** - Finish.

## Binary search program in c

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
#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 of program:**

This **Searching Technique in Data Structures **used for finding an element in a data set of a data.

Searching Technique in Data Structures

Searching Technique in Data Structures

## Leave a Reply