# 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/2K

The iteration will stop when N/2K = 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(log2(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 log2(N).

### Space Complexity

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