Binary search algorithm:
Binary search requires sorted list to perform searching. First find the
lower index and upper index of an array and calculate mid with the formula
(lower+upper)/2.Compare the search element with mid position element. If both are equal then
stop the search process. If both are not equal then divide list into two parts. If the search element
is less than mid position element then change the upper index value and use first half of the list
for further searching process. If the search element is greater than mid position element than
change the lower index value and use second half of the list for further searching process. Again
find lower and upper index value and calculate mid value. Repeat the process till element is found
or lower index value is less than or equal to upper index value.
H.W. Find the position of element 29 using binary search method in an array ‘A’
given
below. Show each step.
A={11,5,21,3,29,17,2,43}
Algorithm
Step 1: Compare key with the middle element of the array.
step 2: If key matches with the middle element, we return the index of the middle element.
step 3: Else if key is greater than the middle element, it means that key can only lie in the right half subarray
after the middle element. So we repeat steps 1 to 4 for the right half subarray and leave the left half subarray.
step 4: Else if key is smaller than the middle element, it means that target can only lie in the left half subarray
before the middle element. So, we repeat steps 1 to 4 for the left half subarray.
step 5: We will keep doing that till we find key or there is no element left in the subarray being considered.
Binary search program
#include <stdio.h>
int main() {
int a[20],f,l,m,i,n,key;
printf("enter number of elements");
scanf("%d",&n);
printf ("\n enter elements");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
printf("enter search key");
scanf("%d",&key);
f=0 ,l=n-1;
m=(f+l)/2;
while(f<=l&&a[m]!=key)
if (key<a[m])
l=m-1;
else
f=m+1;
m=(f+l)/2;
if(a[m]==key)
printf("search key is found at position %d",m+1);
else
{
printf("key is not exist in array");
return 0;
Time complexity of Binary Search is O(log n), where n is the number of elements in the array. It
divides the array in half at each step. Space complexity is O(1) as it uses a constant amount of extra
space.
Best Case Time Complexity of Binary Search Algorithm: O(1)
Best case is when the element is at the middle index of the array. It takes
only one comparison to find the target element. So the best case
complexity is O(1).
Average Case Time Complexity of Binary Search
Algorithm: O(log N)
An element at index N/2 can be found in 1 comparison
Elements at index N/4 and 3N/4 can be found in 2 comparisons.
Elements at indices N/8, 3N/8, 5N/8 and 7N/8 can be found in 3
comparisons and so on.
Worst Case Time Complexity of Binary Search
Algorithm: O(log N)
The worst case will be when the element is present in the first position. As
seen in the average case, the comparison required to reach the first
element is logN. So the time complexity for the worst case is O(logN).
