DAA PROGRAM BINARY SEARCH
theory:
Binary search algorithm
Generally, to find a value in unsorted array, we should look through
elements of an array one by one, until searched value is found. In case
of searched value is absent from array, we go through all elements. In
average, complexity of such an algorithm is proportional to the length
of the array.
Situation changes significantly, when array is sorted. If we know it, random access capability can be utilized very efficiently to find searched value quick. Cost of searching algorithm reduces to binary logarithm of the array length. For reference, log2(1 000 000) ≈ 20. It means, that in worst case,
algorithm makes 20 steps to find a value in sorted array of a million
elements or to say, that it doesn't present it the array.
Algorithm
Algorithm is quite simple. It can be done either recursively or iteratively:
- get the middle element;
- if the middle element equals to the searched value, the algorithm stops;
- otherwise, two cases are possible:
- searched value is less, than the middle element. In this case, go to the step 1 for the part of the array, before middle element.
- searched value is greater, than the middle element. In this case, go to the step 1 for the part of the array, after middle element.
Now we should define, when iterations should stop. First case is when
searched element is found. Second one is when subarray has no elements.
In this case, we can conclude, that searched value doesn't present in
the array.
Examples
Example 1. Find 6 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.
Step 1 (middle element is 19 > 6): -1 5 6 18 19 25 46 78 102 114
Step 2 (middle element is 5 < 6): -1 5 6 18 19 25 46 78 102 114
Step 3 (middle element is 6 == 6): -1 5 6 18 19 25 46 78 102 114
Example 2. Find 103 in {-1, 5, 6, 18, 19, 25, 46, 78, 102, 114}.
Step 1 (middle element is 19 < 103): -1 5 6 18 19 25 46 78 102 114
Step 2 (middle element is 78 < 103): -1 5 6 18 19 25 46 78 102 114
Step 3 (middle element is 102 < 103): -1 5 6 18 19 25 46 78 102 114
Step 4 (middle element is 114 > 103): -1 5 6 18 19 25 46 78 102 114
Step 5 (searched value is absent): -1 5 6 18 19 25 46 78 102 114
Complexity analysis
Huge advantage of this algorithm is that it's complexity depends on the array size logarithmically in worst case. In practice it means, that algorithm will do at most log2(n) iterations, which is a very small number even for big arrays. It can be proved very easily. Indeed, on every step the size of the searched part is reduced by half. Algorithm stops, when there are no elements to search in. Therefore, solving following inequality in whole numbers:
n / 2iterations > 0
resulting initerations <= log2(n).
It means, that binary search algorithm time complexity is O(log2(n)).
Input:
#include<stdio.h>
int binarySearch(int a[10],int key,int low,int upper);
int main()
{
int a[10],i,key,upper=9,lower=0,pos;
printf("Enter the 10 Elements:");
for(i=0;i<10;i++)
{
scanf("%d",&a[i]);
}
printf("Enter the key Element:");
scanf("%d",&key);
pos= binarySearch(a,key,lower,upper);
if(pos==-1)
printf("\n\t Key Element is not found:");
else
printf("key element found at %d location",pos+1);
return 0;
}
int binarySearch(int a[10],int key,int lower,int upper)
{
if(lower<=upper)
{
int mid=(lower+upper)/2;
if(a[mid]==key)
return mid;
else
if (a[mid]>key)
return(binarySearch(a,key,lower,mid-1));
else
return(binarySearch(a,key,mid+1,upper));
}
return -1;
}
int binarySearch(int a[10],int key,int low,int upper);
int main()
{
int a[10],i,key,upper=9,lower=0,pos;
printf("Enter the 10 Elements:");
for(i=0;i<10;i++)
{
scanf("%d",&a[i]);
}
printf("Enter the key Element:");
scanf("%d",&key);
pos= binarySearch(a,key,lower,upper);
if(pos==-1)
printf("\n\t Key Element is not found:");
else
printf("key element found at %d location",pos+1);
return 0;
}
int binarySearch(int a[10],int key,int lower,int upper)
{
if(lower<=upper)
{
int mid=(lower+upper)/2;
if(a[mid]==key)
return mid;
else
if (a[mid]>key)
return(binarySearch(a,key,lower,mid-1));
else
return(binarySearch(a,key,mid+1,upper));
}
return -1;
}
Output:
pgcomp@pgcomp-OptiPlex-745:~$ gcc binary.c
pgcomp@pgcomp-OptiPlex-745:~$ ./a.out
Enter the 10 Elements:2
4
5
6
9
8
5
1
3
7
Enter the key Element:5
key element found at 3
pgcomp@pgcomp-OptiPlex-745:~$ ./a.out
Enter the 10 Elements:2
4
5
6
9
8
5
1
3
7
Enter the key Element:5
key element found at 3
Hello,
ReplyDeletewelcome to technechhacks where problems are been solved,
We deal with the total functioning of sites like
+ SOCIAL MEDIA (Facebook, twitter, Instagram, Snapchat etc.)
+ BANK ACCOUNTS.
+ ICLOUD.
+ CRIMINAL RECORDS.
+ SCHOOL GRADES.
+ CREDIT SCORES.
+ SPOUSES PHONES.
+ BINARY RECOVERY.
+ BTC MINING etc.
Thus Beware of scammers because most persons are been scammed and they end up getting all solutions to their cyber bullies and attacks by US.
I am Jason Williams one of the leading hack agents.
PURPOSE IS TO GET YOUR JOBS DONE AT EXACTLY NEEDED TIME REQUESTED!!
And our WORK SUCCESS IS 100%!!!
I'm always available for you when you need help.
Contact or write us on:
technechhacks@gmail.com or
intelcorehacks@gmail.com
Thanks for your time.