Binary search is a searching algorithm, used to tell the position of a value that is stored in an array. It is called a binary search because in order to search the value it divides the array into 2 parts.
What is Binary Searching?
It is a searching algorithm that can only be applied on a sorted array. In binary search we first find the middle element of the array by dividing it into two parts (lower half array and upper half array) then compare it with our target element, if the target element is equal to the middle element of array, we return the element position plus one because elements store in array use indexing which starts from 0. If the target element is smaller than middle element then we again divide the lower half array into two parts and compare the middle element with the target element, we will continue to do this process until the middle element, found equal to the target element. If the target element is larger than middle element then we again divide the upper half array into two parts and compare the middle element with the target element, we will continue to do this process until the middle element, found equal to the target element In programming, we can perform the repetitive action by using two tools which are iteration and recursion. In iteration, we use loops such as for, while and do-while and in recursion, we use recursion function.
Binary Search Time Complexity:
Best Case: O(1) Worst Case: O(log n)
Advantages of Binary Search:
- It uses the divide and conquers technique
- It is faster than a linear search
- Already present in the many libraries
- Easy to implement
Disadvantages of Binary search
- It works only on a sorted array
Binary Search in C
Here we have provided a binary search program in C using iterators and Recursion:
C iterative Binary Search:
In Iterative Binary search we will use while loop.
#include <stdio.h>
#include<conio.h>
int main()
{
int i, f, l, mid, num, tar, arr[100];
clrscr();
printf("How many numbers you want to enter in the array: ");
scanf("%d",&num);
printf("Please Enter Elements in Ascending order\n");
for (i = 0; i < num; i++)
scanf("%d",&arr[i]);
printf("Enter the number which position you want to know: ");
scanf("%d", &tar);
f = 0;
l = num - 1;
mid = (f+l)/2;
while (f <= l) {
if (arr[mid] < tar)
f = mid + 1;
else if (arr[mid] == tar) {
printf("%d is at %d position\n", tar, mid+1);
break;
}
else
l = mid - 1;
mid = (f + l)/2;
}
if (f> l)
printf("This element is not in the Array");
getch();
}
Output:
How many numbers you want to enter in the array: 6 Please Enter Elements in Ascending order 12 23 34 45 56 67 Enter the number which position you want to know: 23 23 is at 2 position
C Recursive binary Search:
In Recursive binary search, we will use the recursion of function.
#include <stdio.h>
#include<conio.h>
int BinarySearch(int arr[], int l, int r, int tar)
{
int mid;
if (r >= l) {
mid = l + (r - l) / 2;
if (arr[mid] == tar)
return mid;
if (arr[mid] > tar)
return BinarySearch(arr, l, mid - 1, tar)
return BinarySearch(arr, mid + 1, r, tar);
}
return -1;
}
void main()
{
int arr[100],i,res,num,tar;
clrscr();
printf("How many Elements you wan to enter in the array: ");
scanf("%d",&num);
printf("Enter Elements in the Ascending order\n");
for(i=0;i<num;i++)
scanf("%d",&arr[i]);
printf("Enter the element which position you want to know: ");
scanf("%d",&tar);
res = BinarySearch(arr, 0, num - 1, tar);
if(res == -1)
printf("The element is not present in array");
else
printf("%d is at %d position", tar,res+1);
getch();
}
Output:
How many Elements you want to enter in the array: 5 Enter Elements in Ascending order 12 224 35 46 68 Enter the element which position you want to know: 46 46 is at 4 position
People are also reading: