Two types of Searching Techniques in Data Structure
1. Linear Search
2. Binary Search
Linear Search Algorithm:
Let array a[n] stores n elements. Determine whether element =’x‘ is present or not.
linsrch(a[n], x)
{
index = 0;
flag = 0;
while (index < n) do
{
if (x == a[index])
{
flag = 1;
break;
}
index ++;
}
if(flag == 1)
printf(“Data found at %d position”, index);
else
printf(“data not found”);
}
A non-recursive program for Linear Search:
#include <stdio.h>
#include <conio.h>
main()
{
int number[25], n, data, i, flag = 0;
clrscr();
printf("\n Enter the number of elements: ");
scanf("%d", &n);
printf("\n Enter the elements:");
for(i = 0; i < n; i++)
scanf("%d", &number[i]);
printf("\n Enter the element to be Searched: ");
scanf("%d", &data);
for( i = 0; i < n; i++)
{
if(number[i] == data)
{
flag = 1;
break;
}
}
if(flag == 1)
printf("\n Data found at location: %d", i+1);
else
printf("\n Data not found ");
}
A Recursive program for linear search:
void linear_search(int a[], int data, int position, int n)
{
if(position < n)
{
if(a[position] == data)
printf("\n Data Found at %d ", position);
else
linear_search(a, data, position + 1, n);
}
else
printf("\n Data not found");
}
void main()
{
int a[25], i, n, data;
printf("\n Enter the number of elements: ");
scanf("%d", &n);
printf("\n Enter the elements:");
for(i = 0; i < n; i++)
{
scanf("%d", &a[i]);
}
printf("\n Enter the element to be seached: ");
scanf("%d", &data);
linear_search(a, data, 0, n);
}
Example 1:
Suppose we have the following unsorted list: 45, 39, 8, 54, 77, 38, 24, 16, 4, 7, 9, 20
If we are searching for:
45, we‘ll look at 1 element before success
39, we‘ll look at 2 elements before success
8, we‘ll look at 3 elements before success
54, we‘ll look at 4 elements before success
77, we‘ll look at 5 elements before success
38 we‘ll look at 6 elements before success
24, we‘ll look at 7 elements before success
16, we‘ll look at 8 elements before success
4, we‘ll look at 9 elements before success
7, we‘ll look at 10 elements before success
9, we‘ll look at 11 elements before success
20, we‘ll look at 12 elements before success
For any element not in the list, we‘ll look at 12 elements before failure.
Example 2:
Let us illustrate linear search on the following 9 elements:
Searching different elements is as follows:
1.3. Searching for x = 7 Search successful, data found at 3rd position.
1.4. Searching for x = 82 Search successful, data found at 7th position.
1.5. Searching for x = 42 Search un-successful, data not found.
Binary Search Algorithm:
Let array a[n] of elements in increasing order, n ≥ 0, determine whether ‘x‘ is present,
and if so, set j such that x = a[j] else return 0.
binsrch(a[], n, x)
{
low = 1; high = n;
while (low < high) do
{
mid = (low + high)/2
if(x < a[mid])
high = mid – 1;
else if (x > a[mid])
low = mid +1;
else return mid;
}
return 0;
}
Binary Search Algorithm Implementation:
Example 1:
Let us illustrate binary search on the following 12 elements:
If we are searching for x = 4: (This needs 3 comparisons)
low = 1, high = 12, mid = 13/2 = 6, check 20
low = 1, high = 5, mid = 6/2 = 3, check 8
low = 1, high = 2, mid = 3/2 = 1, check 4, found
If we are searching for x = 7: (This needs 4 comparisons)
low = 1, high = 12, mid = 13/2 = 6, check 20
low = 1, high = 5, mid = 6/2 = 3, check 8
low = 1, high = 2, mid = 3/2 = 1, check 4
low = 2, high = 2, mid = 4/2 = 2, check 7, found
If we are searching for x = 8: (This needs 2 comparisons)
low = 1, high = 12, mid = 13/2 = 6, check 20
low = 1, high = 5, mid = 6/2 = 3, check 8, found
If we are searching for x = 9: (This needs 3 comparisons)
low = 1, high = 12, mid = 13/2 = 6, check 20
low = 1, high = 5, mid = 6/2 = 3, check 8
low = 4, high = 5, mid = 9/2 = 4, check 9, found
If we are searching for x = 16: (This needs 4 comparisons)
low = 1, high = 12, mid = 13/2 = 6, check 20
low = 1, high = 5, mid = 6/2 = 3, check 8
low = 4, high = 5, mid = 9/2 = 4, check 9
low = 5, high = 5, mid = 10/2 = 5, check 16, found
Example 2:
Let us illustrate binary search on the following 9 elements:
Solution:
The number of comparisons required for searching different elements is as follows:
1. If we are searching for x = 101: (Number of comparisons = 4)
low high mid
1 9 5
6 9 7
8 9 8
9 9 9
Found
2. Searching for x = 82: (Number of comparisons = 3)
low high mid
1 9 5
6 9 7
8 9 8
Found
No element requires more than 4 comparisons to be found. Summing the comparisons
needed to find all nine items and dividing by 9, yielding 25/9 or approximately 2.77
comparisons per successful search on the average.
Thus the average number of element comparisons for an unsuccessful search is:
(3 + 3 + 3 + 4 + 4 + 3 + 3 + 3 + 4 + 4) / 10 = 34/10 = 3.4
Time Complexity:
The time complexity of binary search in a successful search is O(log n) and for an unsuccessful search is O(log n).
A non-recursive program for binary search:
# include <stdio.h>
# include <conio.h>
main()
{
int number[25], n, data, i, flag = 0, low, high, mid;
printf("\n Enter the number of elements: ");
scanf("%d", &n);
printf("\n Enter the elements in ascending order: ");
for(i = 0; i < n; i++)
scanf("%d", &number[i]);
printf("\n Enter the element to be searched: ");
scanf("%d", &data);
low = 0; high = n-1;
while(low <= high)
{
mid = (low + high)/2;
if(number[mid] == data)
{
flag = 1;
break;
}
else
{
if(data < number[mid])
high = mid - 1;
else
low = mid + 1;
}
}
if(flag == 1)
printf("\n Data found at location: %d", mid + 1);
else
printf("\n Data Not Found ");
}
A recursive program for binary search:
#include<stdio.h>
#include<conio.h>
void bin_search(int a[], int data, int low, int high)
{
int mid ;
if( low <= high)
{
mid = (low + high)/2;
if(a[mid] == data)
printf("\n Element found at location: %d ", mid + 1);
else
{
if(data < a[mid])
bin_search(a, data, low, mid-1);
else
bin_se arch(a, data, mid+1, high);
}
}
else
printf("\n Element not found");
}
void main()
{
int a[25], i, n, data;
printf("\n Enter the number of elements: ");
scanf("%d", &n);
printf("\n Enter the elements in ascending order: ");
for(i = 0; i < n; i++)
scanf("%d", &a[i]);
printf("\n Enter the element to be searched: ");
scanf("%d", &data);
bin_search(a, data, 0, n-1);
}
Comments
Post a Comment