Binary Search Algorithm : Searching Algorithm

on

 What is Binary Search Algorithm?


Binary Search Algorithm is a Searching Algorithm, it is a fast searching Algorithm with a run-time complexity of Ο(log n). But to work this Algorithm properly there are some pre-condition that is the array should be sorted (in ascending values). It works on the principle of Divide & Conquer.

Binary Search Algorithm compares the middle element with the element you wanted to search if its a match, it returns the index of the element. When not, then if the middle element is greater than the item, then the item is searched in the sub-array to the left of the middle element otherwise then the item is searched on the right side of the middle element. The search continues until the sub-array index comes to zero / item is search.

How Binary Search Works?

The array is sorted before Binary Search Algorithm works, it gets the middle element by a formula - 
mid =(high + low)/2

Let's consider an array [2, 4, 5, 7, 9] (a sorted array), according to the above formula the index of the mid-array element is mid = 2, let's check how:

mid =(4 + 0)/2

So the mid element is 5 [with index '2'], now we compare mid element with the element we want to search for i.e 7. But it's not a match, so check for either the mid element is greater or smaller than the search element; In this case, the mid element is smaller than the search element greater then we consider for the right side sub-array.

[5,7,9]

This is the right-side sub-array now we change the lower index & higher index with the formula 

low = mid + 1
mid =(high + low)/2

So now the lower index is low = 5 & mid = 7, so now we compare mid element with the search element, in this case, the match is found so we exit from the loop and print on the console
print("Match Found at Index = %d", mid)

So we learn the working of the Binary Search Algorithm.

What is the Space & Time Complexity?

The Time Complexity for Binary Search Algorithm is ÎŸ(log n), while the Space Complexity for Binary Search Algorithm is ÎŸ(1).

Code for Binary Search Algorithm in C Language :

#include <stdio.h>
int main()
{
int i, low, high, mid, key, n = 5;
int array[5] = [2, 4, 5, 7, 9];
printf("Enter value to find n");
scanf("%d", &key);
low = 0;
high = n - 1;
mid = (low+high)/2;
while (low <= high) {
if(array[mid] < key)
low = mid + 1;
else if (array[mid] == key) {
printf("%d found at %d",key,mid+1);
break;
}
else
high = mid - 1;
mid = (low + high)/2;
}
if(low > high)
printf("%d Not found !!", key);
return 0;
}

In above, we have the code with the best case & the worst case. 

Social Media:

Do Share ðŸ”— with your friends to show how easy is Binary Search Algorithm.
Leave a comment ðŸ’¬ as feedback for us.
Subscribe to my Blog,😊 (it won't cost you)

Check My Portfolio : Prathmesh Chaudhari

Comments

Post a Comment