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(N2).
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