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

- Let X be the element that we want to search in arr of size N.
- Set start = 0 and end = N – 1.
- 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.

- If the program reaches this stage then that means X is not found in arr.
- 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

- If start <= end then
- 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 elements on the left side of mid.
- Return binary_search(mid+1, end, X)

- If X is less than arr[mid] then
- Reject elements on the right side of mid.
- Return binary_search(start, mid-1, X)

- 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_{2}(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_{2}(N).

### Space Complexity

Non-recursive implementation: O(1).

Recursive implementation: O(log_{2}(N)).

**Read**

Why binary search is better than ternary search?

Binary Search Real Life Examples

**Reference**

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