Searching techniques.
Searching -
Searching Algorithms are designed to check for an element or retrieve an element from any data structure where it is stored.
Based on the type of search operation, these algorithms are generally classified into two categories:
Types
1-> linear search
2-> binary search
1■>linear / sequenctional searching
Technique=>
In this, the list or array is traversed sequentially and every element is checked.
For example:
Linear Search to find the element “20” in a given list of numbers.
■ ) Program to implement linear search->
#include<stdio.h>
#include<conio.h>
void main()
{
int arr[20],N,i,item;
int flag=0;
clrscr();
printf("Enter the size of array=");
scanf("%d",&N);
printf("Enter the elements =");
for(i=0; i<N; i++)
{
scanf("%d",&arr[i]);
}
printf("Elements are=");
for(i=0; i<N; i++)
{
printf("%d\n",arr[i]);
}
printf("Enter the item to be search=");
scanf("%d",&item);
for(i=0; i<N; i++)
{
if(arr[i]==item)
{
flag=1;
break;
}
}
if(flag==1)
{
printf("element found at the position=%d",i+1);
}
else
{
printf("element is not found.");
}
getch();
}
■) Output ->
■) Advantages of Linear Search:
1●Linear search can be used irrespective of whether the array is sorted or not.
2●It can be used on arrays of any data type.
3●Does not require any additional memory.
4●It is a well-suited algorithm for small datasets.
■) Drawbacks of Linear Search:
● Linear search has a time complexity of O(N), which in turn makes it slow for large datasets.
●Not suitable for large arrays.
■) When to use Linear Search?
When we are dealing with a small dataset.
When you are searching for a dataset stored in contiguous memory.
■) Complexity Analysis of Linear Search:
Time Complexity:
1->Best Case: In the best case, the key might be present at the first index. So the best case complexity is O(1)
2->Worst Case: In the worst case, the key might be present at the last index i.e., opposite to the end from which the search has started in the list. So the worst-case complexity is O(N) where N is the size of the list.
3->Average Case: O(N)
Auxiliary Space:
O(1) as except for the variable. to iterate through the list, no other variable is used.
2■>binary search technique=>
These algorithms are specifically designed for searching in sorted data-structures. These type of searching algorithms are much more efficient than Linear Search as they repeatedly target the center of the search structure and divide the search space in half.
■) program to implement binary search->
#include<stdio.h>
#include<conio.h>
void main()
{
int arr[20],N,i,item,first,last,mid;
int flag=0;
clrscr();
printf("Enter the size of array=");
scanf("%d",&N);
printf("Enter the elements in ascending order=");
for(i=0; i<N; i++)
{
scanf("%d",&arr[i]);
}
printf("Elements are=");
for(i=0; i<N; i++)
{
printf("%d\n",arr[i]);
}
printf("Enter the item to be search=");
scanf("%d",&item);
first=0;
last=N-1;
while(first<=last)
{
mid=(first+last)/2;
if(item==arr[mid])
{
flag=1;
break;
}
else
{
if(item>arr[mid])
{
first=mid+1;
}
else
{
last=mid-1;
}
}
}
if(flag==1)
{
printf("element found at the position=%d",mid+1);
}
else
{
printf("element is not found.");
}
getch();
}
■) Output->
■) Conditions for when to apply Binary. Search in a Data Structure:
● The data structure must be sorted.
● Access to any element of the data structure.
■》Complexity Analysis of Binary Search:
Time Complexity:
1->Best Case: O(1)
2->Average Case: O(log N)
3->Worst Case: O(log N)
■ ) Auxiliary Space:
O(1), If the recursive call stack is considered then the auxiliary space will be O(logN).
■) Advantages of Binary Search:
1->Binary search is faster than linear search, especially for large arrays.
2->More efficient than other searching algorithms with a similar time complexity, such as interpolation search or exponential search.
3->Binary search is well-suited for searching large datasets that are stored in external memory, such as on a hard drive or in the cloud.
■) Drawbacks of Binary Search:
1->The array should be sorted.
2->Binary search requires that the data structure being searched be stored in contiguous memory locations.
3->Binary search requires that the elements of the array be comparable, meaning that they must be able to be ordered.
■) Applications of Binary Search:
● Binary search can be used as a building block for more complex algorithms used in machine learning.
● such as algorithms for training neural. ● networks or finding the optimal.
● hyperparameters for a model.
● It can be used for searching in computer graphics such as algorithms for ray tracing. Or texture mapping.
●It can be used for searching a database.takes constant time.
Comments
Post a Comment