Searching in Data Structure
What is a Data Structure?
A Data Structure is a way of collecting and organising data in such a way that we can perform various operations on it.
Why Data Structure is important?
Data Structures are important because they make it easier for computers to process large, complex sets of information. By logically organising data elements, data structure increases the efficiency of computer code .
What is Searching ?
Searching is an operation or a technique that helps finds the place of a given element or value in the list.
Types Of Searching:
1.Linear Search Algorithm (Sequential Search Algorithm):-
Linear search algorithm is also called as sequential search algorithm that starts at one end and goes through each element of a list until desired element is found; otherwise the search continues till the end of the dataset.
Algorithm For Linear Search :-
Step 1: set pos = -1
Step 2: set i = 1
Step 3: repeat step 4 while i <= n
Step 4: if a[i] == val
set pos = i
print pos
go to step 6
[end of if]
set i = i + 1
[end of loop]
Step 5: if pos = -1
print "value is not present in the array "
[end of if]
Step 6: exit
Example For Linear Search :-
Advantages of Linear search:
1. Easy to understand
2. No special data structure required
3. Can be used on unsorted data
4. No additional memory required
5. Not affected by data size
Disadvantages of Linear search:
1. Time-consuming
2. Not suitable for large data sets
3. Not suitable for ordered data
4. Not suitable for repetitive task
5. Not suitable for real-time applications
Code for linear Search :-
#include<stdio.h>
int main ()
{
int size;
int arr[100];
int i,key,pos=-1;
printf("Enter the number of Elements : ");
scanf("%d",&size);
printf("Enter the elements of array : ");
for(i=0;i<size;i++){
scanf("%d",&arr[i]);
}
printf("Enter the number of elements you want to search : ");
scanf("%d",&key);
for(i=0;i<size;i++){
if (arr[i]==key){
pos=i;
printf("Element found at position : %d",pos+1);
}
}
if(pos==-1){
printf("Element not found in the array !");
}
return 0;
}
Output :
1.Binary Search :-
Binary Search is an efficient searching algorithm used to find the position of a target element in a sorted array.
-
It’s called binary because it divides the search space into two halves at every step.
-
Unlike linear search, which checks elements one by one, binary search cuts the search area in half repeatedly, making it much faster.
In binary search we have 3 formulas that we need to use
Mid = low + high / 2
Low = mid + 1 This formula is used when the key element is larger than the mid element (a[mid] < Value/Key)
High = Mid – 1 This formula is used when the key element is smaller than the mid element (a[mid] > Value/Key)
Algorithm For Binary Search :-
Step1: Set Low = Lower bound, High = Upper bound, Pos = -1
Step2: Repeat step 3 & 4 while low <= high
Step3: Set mid = (low + high)/2
Step4: if a[mid]==val
Set pos = mid
Print pos
Go to step 6
else if a[mid] >val
Set high = mid-1
else Set low = mid+1
[End of if]
[End of loop]
Step 5: if pos=-1
Print “Value is not present in the array”
[End of if]
Step6: Exit
Example For Binary Search :-
Advantages of Binary search:
- Binary search is faster than linear search, especially for large arrays.
- More efficient than other searching algorithms with a similar time complexity, such as interpolation search or exponential search.
- 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.
Disadvantages of Binary search:
- The array should be sorted.
- Binary search requires that the data structure being searched be stored in contiguous memory locations.
- Binary search requires that the elements of the array be comparable, meaning that they must be able to be ordered.
Code for Binary Search :-
#include <stdio.h>
int main() {
int size, i, key, low, high, mid, pos = -1;
int arr[100];
printf("Enter the number of elements: ");
scanf("%d", &size);
printf("Enter the elements of array in sorted order: ");
for (i = 0; i < size; i++) {
scanf("%d", &arr[i]);
}
printf("Enter the element you want to search: ");
scanf("%d", &key);
low = 0;
high = size - 1;
while (low <= high) {
mid = (low + high) / 2;
if (arr[mid] == key) {
pos = mid;
break;
}
else if (arr[mid] < key) {
low = mid + 1;
}
else {
high = mid - 1;
}
}
if (pos != -1) {
printf("Element found at position: %d\n", pos);
}
else {
printf("Element not found in the array!\n");
}
return 0;
}
Output :
0 Comments