In this tutorial we will study different Searching Technique in Data Structures.
- 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
- Linear searching
- Binary searching
Let’s start with studying different Searching Technique in Data Structures.
- Linear searching is a simple type of searching where we find the element from the set of element from beginning to end.
- The linear searching 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 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.
Consider, The following set of elements having the 10 elements stored in array in a linear way.
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 algorithm
- Define array of a element.
- Take input from 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 a array found then print not found.
Linear search program
int num,find,I,flag=0; //declare array and finding value
printf(“Enter 10 values to array:”);
scanf(“%d”, &num[i]); //take input from user in array num
printf(“Enter number to check in array:”);
scanf(“%d”,&find); //take search value in find variable
for(i=0;i<10;i++) //itrate loop till 10 values in num array
if(num[i]==find) //check that find number in array
flag=1; //if it is in array set the flag
printf(“Number found in array :”);
Output of program:
Enter 10 values to array:
1 2 3 4 5 6 7 8 9 10
Enter Number to Search:
Number is Found.
- 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.
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.
In this, Start = 5 and end = 9
Find, mid= 5+9/2 =7
In this case finding element is less than mid value, so we will find in left portion.
end = mid-1
Start = 5 and end = 6
Find, mid= 5+6/2 = 5
In this finding element is greater than middle element so we will find in right portion.
Start = mid+1
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.
Binary search algorithm
- Take a number of Array element user want.
- Take the array elements from 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.
- Calculate 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.
Binary search program
int a,start,end,mid ,n,i,item; //declaring the variable
printf(“Enter number of elements:”);
//limit of the array
scanf(“%d”,&a[i]); //Enter values in the array and value should be in sorted order.
printf(“Enter element to search:”);
start=0; //set start point to 0
end=n-1; //set end point to last
mid=(start+end)/2; //find the middle of the array
while(item!=a[mid] && start<=end) //finding on array the search value.
if(item> a[mid]) //check that search value is greater than the middle value in array
start=mid+1; //if search value is greater then set the value after middle as starting point
end=mid-1; //if search value is less then set the value before middle as end point
mid=(start+end)/2; //find mid value till one value left in array
printf(%d found at a position %d :”,item,mid+1);
printf(“%d is not found in array:”,item);
Output of program:
Enter number of elements:
10 20 30 40 50
Enter element to search:
40 found at position 4:
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