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 element in a data set of a 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**

1. Linear search is a simple type of searching where we find the element from the set of element from beginning to end.

2. The linear search is a sequential searching for finding value in a list.

3. In this, We (check) find the element from starting element and continues to check until the finding element to be found with in list and this process done till the last and if there is no such element then their is no element found in a list.

**Linear search example **

Consider, The following set of elements having the 10 elements stored in 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 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 a array.

In this way find **120** in a 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 end of array and no match of element we finding in array therefore there is a no finding element available in a array.

In this way we perform linear searching of a data now we write a algorithm for linear searching.

**Linear search complexity**

Time complexity for linear search is log(N^{2}).

**Linear search algorithm**

1. Define array of a element.

2 .Take input from user which want to search.

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

4. If the last element reached then no element in a array found then print **not found.**

**Linear search program in data structure**

123456789101112131415161718192021222324252627282930 | #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 a another method for finding element in 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 a array and if it is greater than the middle element then we search in right portion of 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 a 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

**Binary search**

**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 element is less than **mid** value, so we will find in 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 binary search now we will see the algorithm for Binary search.

**Linear search complexity**

Time complexity for linear search is log(N).

**Binary search algorithm**

1. Take a number of Array element user want.

2. next Take the array elements from user in ascending order only.

3. Take a finding element from a user.

4. Set start = 0 and end= last element of an array.

5. Then calculate a mid value = (Start+end/2)

6. Compare mid value with finding value.

7. Check mid value less than finding value if **yes** set **start to mid+1. **If not, Then set **end = mid -1.**

8. mid values and continue with step 6 until one mid value left (there is no left or right portion left)

9. If that one mid value is equal to finding element print **number found.**

10. If start > end print **number not found.**

11. Finish.

**Binary search program in c**

1234567891011121314151617181920212223242526272829303132333435363738 | #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 element in a data set of a data.

Searching Technique in Data Structures

Searching Technique in Data Structures