Binary Search

Binary search is a searching algorithm that searches an element in a sorted array in O(logN) complexity. It is also known as half-interval search, logarithmic search, or binary chop search.

Binary Search Algorithm

We are assuming that the array is sorted in ascending order.

The binary search algorithm is based on the principle that if we have a sorted array arr (ascending order) and we compare ith index value with another value X. Then if arr[i] is smaller than X then it means all the values on the left side of arr[i] are also smaller than X. Similarly, If arr[i] is greater than X, then all the values of the right side of arr[i] are also larger than X.

Based on the above principle, the binary search algorithm compares the search value X with the middle element of the array and keep eliminating the left-hand or the right-hand side until we find X or the size of the array becomes one. The effective size of the array decreases by 2 on each iteration.

For Example,
Let 20 be the value we want to search

Steps to implement Binary Search Algorithm

1. Let X be the element that we want to search in arr of size N.
2. Set start = 0 and end = N – 1.
3. Repeat the following steps while start <= end
   • Set mid = (start + end) / 2.
   • If X is equal to arr[mid] then
     • X is present in arr at index mid.
     • Return mid.
   • If X is greater than arr[mid] then
     • Reject all elements on the left side of mid.
     • Set start = mid + 1
   • If X is less than arr[mid] then
     • Reject all elements on the right side of mid.
     • Set end = mid – 1.
4. If the program reaches this stage then that means X is not found in arr.
5. Return -1.

If the search is successful, then the function returns the index of X otherwise it returns -1.

Pseudo Code

arr: sorted array
n: size of array
x: element we want to search in arr
FUNCTION binary_search(arr,n,x)
	start := 0
	end := n-1
	WHILE start<=end
      		mid:= (start+end)/2
      		IF arr[mid] == x
			return mid
		ELSE IF arr[mid] < x
			start := mid + 1
		ELSE
			end := mid - 1
		END
	END
	return -1
END

Program of Binary search in c/c++

#include<stdio.h>

int binary_search(int arr[],int n,int x){
	int start = 0;
	int end = n-1;
	while(start<=end){
		int mid = (start+end)/2;
		if(arr[mid]==x)	
			return mid;
		else if(arr[mid]<x)	
			start = mid + 1;
		else	
			end = mid - 1;
	}
	return -1;
}

int main()
{		
	   int arr[] = {1,3,4,5,6,7,8,10,14,15,18};
	   int n = 11;
	   int index;
	   int x;
	   
	   printf("Enter element you want to search: ");
	   scanf("%d",&x);
	   
	   index = binary_search(arr,n,x);
	   
	   if(index!=-1){
	   		printf("%d%s%d",x," is present at index ",index);
	   }
	   else{
	   		printf("%d%s",x," is not present in the given array\n");
	   }
	   
}

Output

Enter element you want to search: 3
3 is present at index 1

Binary Search Algorithm Recursive Implementation

The recursive binary search function accepts 4 parameter.

int binary_searchR(start, end, X, arr);

start and end define the range in which we want the value X in array arr.

Steps

1. If start <= end then
   1. Set mid = (start + end) / 2.
   2. If X is equal to arr[mid] then
      • X is present in arr at index mid.
      • Return mid.
   3. If X is greater than arr[mid] then
      • Reject elements on the left side of mid.
      • Return binary_search(mid+1, end, X)
   4. If X is less than arr[mid] then
      • Reject elements on the right side of mid.
      • Return binary_search(start, mid-1, X)
2. Return -1.

Pseudo Code

FUNCTION binary_search(start, end, arr, x)
	IF start<=end THEN
      	mid:= (start+end)/2
      	IF arr[mid] == x
			return mid
		ELSE IF arr[mid] < x
			return binary_search(mid+1, end, arr, x)
		ELSE
			return binary_search(start, mid-1, arr, x)
		END
	END
	return -1
END

Program of Binary search using recursion in c/c++

#include<stdio.h>

int binary_search(int arr[],int start,int end,int x){
	if(start<=end){
		int mid = (start+end)/2;
		if(arr[mid]==x)	
			return 	mid;
		else if(arr[mid]<x)	
			return 	binary_search(arr,mid+1,end,x);
		else	
			return	binary_search(arr,start,end-1,x);
	}
	return -1;
}

int main()
{		
	   int arr[] = {1,3,4,5,6,7,8,10,14,15,18};
	   int n = 11;
	   int index;
	   int x;
	   
	   printf("Enter element you want to search: ");
	   scanf("%d",&x);
	   
	   index = binary_search(arr,0,n-1,x);
	   
	   if(index!=-1){
	   		printf("%d%s%d",x," is present at index ",index);
	   }
	   else{
	   		printf("%d%s",x," is not present in the given array\n");
	   }
	   
}

Output

Enter element you want to search: 15
15 is present at index 9

Note:

• The above code/algorithm is for the arrays sorted in ascending order.
• If the array is sorted in descending order, then we just need to swap start = mid + 1 and end = mid – 1.

Time Complexity

Method 1

• It is clear that on every iteration the size of the array is reduced by half.
• The worst-case is when the element is not present in the array.

Suppose N is the size of the array

• After 1st iteration
  Size of Array = N/2
• Similarly, 2nd Iteration
  Size of Array = N/4
  …..
  …..
• Thus, for Kth iteration
  Size of Array = N/2^K

The iteration will stop when N/2^K = 1

N/2^K = 1
2^K = N
K = log(N)

Thus, in the worst case, we will require K = log(N) comparisons. Therefore, the time complexity is O(log₂(N)).

Method 2

The recurrence relation for binary search is

T(N) = T(N/2) + C
where C is a constant and T(N) is the time required to search an array of size N using Binary Search.

Now, we can write
T(N) = T(N/2^1) + C	…1
T(N/2) = T(N/2^2) + C	…2
T(N/4) = T(N/2^3) + C	…3
…..	
…..	
T(2) = T(N/2^K) + C	…k
where N/2^K = 1
On adding above equations from 1 to k , we get
T(N) = T(N/2^K) + KC        …(a)
N/2^K = 1
K = log(N)
Therefore, T(N) = T(1) + log2(N)*C
Since, T(1) and C are constant, we can ignore them
T(N) = log2(N)

Hence, the time complexity is log₂(N).

Space Complexity

Non-recursive implementation: O(1).
Recursive implementation: O(log₂(N)).

Read
Why binary search is better than ternary search?
Binary Search Real Life Examples

Reference
https://en.wikipedia.org/wiki/Binary_search_algorithm