Binary Search

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 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;
}

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)

If the array is non-increasing or non-decreasing then we can use binary search.