Suppose we are given a sorted array (0-based indexing) a = {10, 32, 34, 40, 50, 100, 101, 102, 104}, and a number k=40. We have to find out the position of this number.
One way is linear search, which is iterating over the array and finding the position of 40. The time complexity of this approach is O(n).
We can do it using a binary search whose complexity is O(logn).
First, we will search in the complete array from 0 to n-1, and we will check for the mid position let’s say the mid position is m.
If we find that a[m] is greater than 40, that means the position of 40 is definitely in the range from 0 to m-1, then we will search from 0 to m-1.
On the other hand, if a[m] is less than 40, that means the position of 40 is definitely in the range from m+1 to n-1, then we will search from 0 to m-1.
This way, we will make the range half.
Binary Search in C
#include <stdio.h>
int main(void) {
int a[10];
int n;
scanf("%d", &n);
for(int i=0;i<n;i++)
{
scanf("%d", &a[i]);
}
int k;
scanf("%d", &k);
int l=0, r=n-1;
while(l<=r){
int m=(l+r)/2;
if(a[m]>k)
{
r=m-1;
}
if(a[m]<k)
{
l=m+1;
}
if(a[m]==k)
{
printf("%d", m);
return 0;
}
}
return 0;
}
This is a C program that performs binary search on an array of integers.
The program first reads in the size of the array and then reads in the elements of the array from the user. It then reads in the value to search for, which is stored in variable k.
The binary search algorithm is implemented using a while loop that continues until l becomes greater than r. In each iteration of the loop, the middle index m between l and r is calculated. If the element at index m is greater than k, then the search is continued in the left half of the array by setting r=m-1. If the element at index m is less than k, then the search is continued in the right half of the array by setting l=m+1. If the element at index m is equal to k, then the index m is printed and the program terminates.
If the element k is not found in the array, the program simply returns 0.
This program demonstrates a basic implementation of the binary search algorithm in C.
If the array has duplicate elements, and if there is more than 1 element equal to k then we want to find the first index. And if there is no element equal to k then print -1. We will change our code according to the below.
#include <stdio.h>
int main(void) {
int a[20];
int n;
scanf("%d", &n);
for(int i=0;i<n;i++)
{
scanf("%d", &a[i]);
}
int k;
scanf("%d", &k);
int l=0, r=n-1;
int ans=-1;
while(l<=r){
int m=(l+r)/2;
if(a[m]>k)
{
r=m-1;
}
if(a[m]<k)
{
l=m+1;
}
if(a[m]==k)
{
if(ans==-1) ans=m;
else if(ans>m) ans=m;
r=m-1;
}
}
printf("%d", ans);
return 0;
}
Binary Search in Python
n=int(input())
a=list(map(int, input().split()))
k=int(input())
l, r=0, n-1
ans=-1
while l<=r:
m=(l+r)//2
if a[m]==k:
ans=m if ans==-1 else min(ans, m)
r=m-1
elif a[m]>k:
r=m-1
elif a[m]<k:
l=m+1
print(ans)This is a Python program that performs a binary search on a list of integers.
The program first reads in the size of the list n and then reads in the elements of the list from the user. It then reads in the value to search for, which is stored in variable k.
The binary search algorithm is implemented using a while loop that continues until l becomes greater than r. In each iteration of the loop, the middle index m between l and r is calculated. If the element at index m is equal to k, then we update the value of ans to be either m or the minimum of ans and m (depending on whether or not ans has already been set), and continue searching in the left half of the list by setting r=m-1. If the element at index m is greater than k, then we continue searching in the left half of the list by setting r=m-1. If the element at index m is less than k, then we continue searching in the right half of the list by setting l=m+1.
Finally, the program prints the value of ans, which is the index of the smallest element in the list that is equal to k. If no such element exists, then ans will be -1.
If the array is non-increasing or non-decreasing then we can use binary search.
