- What is Binary Search?
- Binary Search Pseudocode
- Binary Search Algorithm
- Binary Search Time Complexity
- Calculating Time complexity of binary search
- Binary Search Space Complexity
- Binary Search in C
- Binary Search in JAVA
- Binary Search in C++
- Binary Search in Python
- Binary Search Example
- Complexity of Searching, Insertion and Deletion in Binary Tree
- Complexity of Searching, Insertion and Deletion in Binary Search Tree (BST)
- Complexity of Searching, Insertion and Deletion in AVL Tree
- Big O for Binary Search
- Running Time of Binary Search
- RB Tree
- Difference between Binary Tree and Binary Search Tree

**What is Binary Search?**

Binary Search Algorithm is one of the widely used searching techniques. It can be used to sort arrays. This searching technique follows the divide and conquer strategy. The search space always reduces to half in every iteration.

Binary Search Algorithm is a very efficient technique for searching but it needs some order on which partition of the array will occur.

**Advantages of Binary Search Algorithm**

- Since it follows the technique to eliminate half of the array elements, it is more efficient as compared to linear search for large data.
- Better time complexity and thus takes less compilation time.
- An improvement over linear search as it breaks the array down in half rather than sequentially traversing through the array elements.

**Limitations of Binary Search Algorithm**

- Binary Search algorithm could only be implemented over a sorted array.
- Small unsorted arrays would take considerate time in sorting and then searching the desired element. So, binary search is not preferred in such cases.
- It has poor locality of reference compared to linear search algorithm when comes to in-memory searching for short intervals.

**Applications of Binary Search**

- This algorithm is used to search element in a given sorted array with more efficiency.
- It could also be used for few other additional operations like- to find the smallest element in the array or to find the largest element in the array.

**Binary Search Pseudocode**

- We are given an input array that is supposed to be sorted in ascending order.
- We take two variables which will act as a pointer i.e, beg, and end.
- Beg will be assigned with 0 and the end will be assigned to the last index of the array.
- Now we will introduce another variable mid which will mark the middle of the current array. That will be computed as (low+high)/2.
- If the element present at the mid index is equal to the element to be searched, then just return the mid index.
- If the element to be searched is smaller than the element present at the mid index, move end to mid-1, and all RHS will get discarded.
- If the element to be searched is greater than the element present at the mid index, move beg to mid+1, and all LHS will get discarded.

**Binary Search Algorithm**

**Iterative approach**

```
binarySearch(arr, size)
loop until beg is not equal to end
midIndex = (beg + end)/2
if (item == arr[midIndex] )
return midIndex
else if (item > arr[midIndex] )
beg = midIndex + 1
else
end = midIndex - 1
```

**Recursive approach**

```
binarySearch(arr, item, beg, end)
if beg<=end
midIndex = (beg + end) / 2
if item == arr[midIndex]
return midIndex
else if item < arr[midIndex]
return binarySearch(arr, item, midIndex + 1, end)
else
return binarySearch(arr, item, beg, midIndex - 1)
return -1
```

**Binary Search Algorithm Dry Run**

- Item to be searched=20

input:

0 | 1 | 2 | 3 | 4 |

10 | 11 | 16 | 20 | 23 |

beg=0, end=4, mid=2

0 | 1 | 2 | 3 | 4 |

10 | 11 | 16 | 20 | 23 |

beg=3, end=4, mid=3

0 | 1 | 2 | 3 | 4 |

10 | 11 | 16 | 20 | 23 |

Element found at index 3, Hence 3 will get returned.

2. Given is the pictorial representation of binary search through an array of size 6 arranged in ascending order. We intend to search the element 78:

**Binary Search Time Complexity**

- In each iteration, the search space is getting divided by 2. That means that in the current iteration you have to deal with half of the previous iteration array.
- And the above steps continue till beg<end
- Best case could be the case where the first mid-value get matched to the element to be searched
- Best Time Complexity: O(1)
- Average Time Complexity: O(logn)
- Worst Time Complexity: O(logn)

**Calculating Time complexity of binary search**

- Let k be the number of iterations.

(E.g. If a binary search gets terminated after four iterations, then k=4.)

- In a binary search algorithm, the array taken gets divided by half at every iteration.
- If n is the length of the array at the first iteration, then at the second iteration, the length of the array will be n/2
- Again dividing by half in the third iteration will make the array’s length = (n/2)/2=n/(2^k).
- Similarly, at the fourth iteration, the value of the array’s length will be n/(2^3). and so on.
- At the kth iteration, the value of the length of the array will be = (n/2^k).

- As after k divisions, the length of the array becomes 1 therefore,

n/(2^k)=1

=> n = 2k

- Applying log function on both sides:

=>log(n) = log (2^k) (log with base 2)

=>log (n) = k log (2) (log with base 2)

As (log (a) = 1) (log with base 2)

Therefore,

=> k = log (base 2) (n)

Therefore, the time complexity of the Binary Search algorithm is log (base 2) n.

**Binary Search Space Complexity**

No auxiliary space is required in Binary Search implementation

The binary search algorithm’s space complexity depends on the way the algorithm has been implemented. Two ways in which it can be implemented are:

**Iterative method**: In this method, the iterations are controlled through looping conditions. The space complexity of binary search in the iterative method is O(1).

**Recursive method**: In this method, there is no loop, and the new values are passed to the next recursion of the loop. Here, the max and min values are used as the boundary condition. The space complexity of binary search in the recursive method is O(log n).

**Binary Search in C **

**Iterative Binary Search in C**

**Code:**

```
#include <stdio.h>
int binarySearch( int arr[], int item, int beg, int end) {
while (beg <= end) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] > item)
beg = midIndex + 1;
else
end = midIndex - 1;
}
return -1;
}
int main(void) {
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
printf("answer: %d", ans);
return 0;
}
```

**Output:**

answer: 1

**Recursive Binary Search in C**

**Code:**

```
#include <stdio.h>
int binarySearch(int arr[], int item, int beg, int end) {
if (end >= beg) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] < item)
return binarySearch(arr, item, beg, midIndex - 1);
return binarySearch(arr, item, midIndex + 1, end);
}
return -1;
}
int main(void) {
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
printf("answer: %d", ans);
return 0;
}
```

**Output:**

answer: 1

**Binary Search in JAVA**

**Iterative Binary Search in JAVA**

**Code:**

```
class BinarySearch {
int binarySearch(int arr[], int item, int beg, int end) {
while (beg <= end) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] > item)
beg = midIndex + 1;
else
end = midIndex - 1;
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = arr.length;
int item = 45;
int ans = ob.binarySearch(arr, item, 0, n - 1);
if (ans == -1)
System.out.println("Element not present");
else
System.out.println("answer: "+ans);
}
}
```

**Output:**

answer: 1

**Recursive Binary Search in JAVA**

**Code:**

```
class BinarySearch {
int binarySearch(int arr[], int item, int beg, int end) {
if (end >= beg) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] < item)
return binarySearch(arr, item, beg, midIndex - 1);
return binarySearch(arr, item, midIndex + 1, end);
}
return -1;
}
public static void main(String args[]) {
BinarySearch ob = new BinarySearch();
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = arr.length;
int item = 45;
int ans = ob.binarySearch(arr, item, 0, n - 1);
if (ans == -1)
System.out.println("Element not present");
else
System.out.println("answer: "+ans);
}
}
```

**Output:**

answer: 1

**Binary Search in C++ **

**Iterative Binary Search in C++ **

**Code:**

```
#include <iostream>
using namespace std;
int binarySearch(int arr[], int item, int beg, int end) {
while (beg <= end) {
int midIndex = beg + (end - beg) / 2;
if (arr[midIndex] == item)
return midIndex;
if (arr[midIndex] > item)
beg = midIndex + 1;
else
end = midIndex - 1;
}
return -1;
}
int main(void) {
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
printf("answer: %d", ans);
}
```

**Output:**

answer: 1

**Recursive Binary Search in C++**

**Code:**

```
#include <iostream>
using namespace std;
int binarySearch(int array[], int item, int beg, int end) {
if (end >= beg) {
int midIndex = beg + (end - beg) / 2;
if (array[midIndex] == item)
return midIndex;
if (array[midIndex] < item)
return binarySearch(array, item, beg, midIndex - 1);
return binarySearch(array, item, midIndex + 1, end);
}
return -1;
}
int main(void) {
int arr[] = {13, 45, 65, 16, 117, 82, 19};
int n = sizeof(arr) / sizeof(arr[0]);
int item = 45;
int ans = binarySearch(arr, item, 0, n - 1);
if (ans == -1)
printf("Element not present");
else
printf("answer: %d", ans);
}
```

**Output:**

answer: 1

**Binary Search in Python**

**Iterative Binary Search in Python**

**Code:**

```
def binarySearch(arr, item, beg, end):
while beg <= end:
mid = beg + (end - beg)//2
if arr[mid] == item:
return mid
elif arr[mid] > item:
beg = mid + 1
else:
end = mid - 1
return -1
arr = [13, 45, 65, 16, 117, 82, 19]
item = 45
ans = binarySearch(arr, item, 0, len(arr)-1)
if ans != -1:
print("answer: " + str(ans))
else:
print("Element not present")
```

**Output:**

answer: 1

**Recursive Binary Search in Python**

**Code:**

```
def binarySearch(arr, item, beg, end):
if end >= beg:
midIndex = beg + (end - beg)//2
if arr[midIndex] == item:
return midIndex
elif arr[midIndex] < item:
return binarySearch(arr, item, beg, midIndex-1)
else:
return binarySearch(arr, item, midIndex + 1, end)
else:
return -1
arr = [13, 45, 65, 16, 117, 82, 19]
item = 45
ans = binarySearch(arr, item, 0, len(arr)-1)
if ans != -1:
print("answer: " + str(ans))
else:
print("Element not present")
```

**Output:**

answer: 1

**Binary Search Example**

**Example1:**

Your task is to find the first and last occurrence of the given element in the array. If an element is not present, return -1. Assuming sorting here is in ascending order.

Example:

Input

7

1 2 5 5 5 5 6

5

Output

2 5

#### Code in Java:

```
import java.util.*;
class Demo {
public static void main ( String[] args ) {
Scanner sc = new Scanner( System.in );
int n = sc.nextInt();
int[] arr = new int[n];
for( int i = 0 ; i < n ; i++ )
{
arr[i] = sc.nextInt();
}
int item = sc.nextInt();
int beg = 0, end = 0;
for( int i = 0 ; i < n ; i++ )
{
if( arr[i] == item )
{
beg = i;
break;
}
else{
beg = -1;
}
}
for( int i = arr.length - 1 ; i > 0; i-- )
{
if( arr[i] == item )
{
end = i;
break;
}
}
if(beg == -1)
{
System.out.println( -1 );
}
else {
System.out.println( beg + " " + end );
}
}
}
```

#### Code in C++:

```
#include <iostream>
using namespace std;
int main(void) {
int n;
cin>>n;
int arr[n];
for( int i = 0 ; i < n; i++)
cin>>arr[i];
int item;
cin>>item;
int beg = 0, end = 0;
for( int i = 0 ; i < n ; i++ )
{
if( arr[i] == item )
{
beg = i;
break;
}
else{
beg = -1;
}
}
for( int i = n - 1 ; i > 0; i-- )
{
if( arr[i] == item )
{
end = i;
break;
}
}
if(beg == -1)
{
cout<<"-1";
}
else {
cout<<beg<<" "<<end;
}
}
```

#### Code in C:

```
#include <stdio.h>
int main() {
int n;
scanf("%d ", &n);
int arr[n];
for( int i = 0 ; i < n; i++)
scanf("%d ",&arr[i]);
int item;
scanf("%d ",&item);
int beg = 0, end = 0;
for( int i = 0 ; i < n ; i++ )
{
if( arr[i] == item )
{
beg = i;
break;
}
else{
beg = -1;
}
}
for( int i = n - 1 ; i > 0; i-- )
{
if( arr[i] == item )
{
end = i;
break;
}
}
if(beg == -1)
{
printf("%d ",-1);
}
else {
printf("%d %d",beg,end);
}
}
```

**Complexity of Searching, Insertion and Deletion in Binary Tree**

A tree is binary when a node can have at most two children.

Let’s define the complexity of searching, insertion & deletion in a binary tree with an example.

E.g. The figure given below is a binary tree.

If we have to search for element 7, we will have to traverse all the elements to reach that element, therefore to perform **searching** in a binary tree, the worst-case complexity= O(n).

If we have to insert an element as the left child of element 7, we will have to traverse all the elements, therefore performing **insertion** in a binary tree, the worst-case complexity= O(n).

If we have to delete element 7, we will have to traverse all the elements to find it, therefore performing **deletion** in a binary tree, the worst-case complexity= O(n).

## Complexity of Searching, Insertion and Deletion in Binary Search Tree (BST)

Binary Search Tree (BST) is considered as a special type of binary tree where the values are arranged in the following order: left child < parent node < right child.

Let’s define the complexity of searching, insertion & deletion in a binary search tree with an example.

E.g. The figure given below is a binary search tree.

If we have to search for element 3, will have to traverse all the elements to reach that element, therefore to perform **searching** in a binary search tree, the worst-case complexity= O(n). In general, the time complexity is O(h) where h = height of binary search tree.

If we have to insert an element 2, we will have to traverse all the elements to insert it as the left child of 3. Therefore, to perform **insertion** in a binary search tree, the worst-case complexity= O(n) whereas the time complexity in general = O(h).

Suppose we have to delete the element 3. In that case, we will have to traverse all the elements to find it, therefore performing **deletion** in a binary tree, the worst-case complexity= O(n) whereas the time complexity in general = O(h).

## Complexity of Searching, Insertion and Deletion in AVL Tree

AVL(**Adelson-Velskii and Landis)** tree is a binary search tree which is also known as height balanced tree as it has a property in which the difference between the height of the left sub-tree and the right sub-tree can never be more than 1.

Let’s define the complexity of searching, insertion & deletion in AVL tree with an example.

E.g. The figure given below is an AVL tree.

If we have to search for element 5, will have to traverse all the elements to reach that element i.e. in the order 30,14,5 = 3 = log n , therefore to perform **searching** in an AVL tree, the worst-case complexity= O(log n).

If we have to insert an element 92, we will have to traverse all the elements in order 30, 42, 71 to insert it as the right child of 71. Therefore, to perform **insertion** in an AVL tree, the worst-case complexity= O(log n).

If we have to delete the element 71, we will have to traverse all the elements to find it in the order 30, 42, 71. Therefore to perform **deletion** in an AVL tree, the worst-case complexity= O(log n).

**Big O for Binary Search**

Big O notation shows the number of operations that an algorithm will perform. It finds the upper bound that gives the worst-case running time complexity. It helps you understand how fast an algorithm is growing and allows you to compare the growth with others.

When the number of steps are counted, you divide the range into half and then process it. This process stops once both the upper and the lower bounds cross. This way you check the entry every time as you have half of the number of entries to check each time. Putting this into a formula as a recurrence T(n) we get:

T(n)=T(n/2)+1 (Binary search recurrence relation)

With base case T(1)=1.

By applying any variant of the Master Theorem, you get

T(n) ∈ O(log (n))

**Running Time of Binary Search**

Binary search halves the size of portion that is reasonable after every incorrect guess. If binary search makes a wrong guess, the portion of the array that contains reasonable guesses is reduced to half. For eg. if the portion had 40 elements then the incorrect guess comes down to 20.

If we start performing binary search on an array of 16 elements then the incorrect guessed will be reduced to length 8, then 4, then 2 and then 1. No more guesses occur once the reasonable portion comes down to just 1. 1 portion element can either be correct or incorrect and we have reached our result. So, for an array of length 16 elements, binary search requires five guesses at most.

Similarly for 32 elements, binary search will require at most 6 guesses to get the answer. We can see a pattern being formed here i.e., we require one more guess to get the result if the number of elements is doubled.

Let there be m number of guesses for an array of length n, then for an array of length 2n, the length cut down after the 1st guess will be n. Now, the number of guesses will become m+1.

(Taking up the general case of an array of length n, we can say that the number of time we are repeatedly reducing the length of n to half until we reach the value 1, plus one. We can write this mathematically with the base-2 logarithm of n.)

The worst case in binary search is achieved when the integers are equal which can be significant when the encoding lengths are large, like large integer types or long strings. This would make the comparison between elements expensive, also comparing the floating-point values are often more expensive than the comparison done between integers or short strings.

**RB Tree**

RB Tree (Red Black Tree) is a self-balancing binary search tree where left child < parent < right child. Each node in the RB tree is either red or black in color. These colors ensure that the tree maintains its balance when insertion or deletion of nodes is performed.

**Properties:**

- Color of the root node is always black.
- Parent node of red color does not contain a red child.
- Every leaf node/NIL is of black color.
- The descendent path from every node have the same black height. (Black Height Rule)

**Time Complexity of RB Tree**

For searching, the time complexity is O(log n).

For insertion, the time complexity is O(log n).

For deletion, the time complexity is O(log n).

**Rotation Operation on RB Tree**

**LR (Left Right) Rotation**

**RR (Right Right) Rotation**

**Insertion in RB Tree**

Algorithm:

```
RB-INSERT (T, z)
1. y ← nil [T]
2. x ← root [T]
3. while x ≠ NIL [T]
4. do y ← x
5. if key [z] < key [x]
6. then x ← left [x]
7. else x ← right [x]
8. p [z] ← y
9. if y = nil [T]
10. then root [T] ← z
11. else if key [z] < key [y]
12. then left [y] ← z
13. else right [y] ← z
14. left [z] ← nil [T]
15. right [z] ← nil [T]
16. color [z] ← RED
17. RB-INSERT-FIXUP (T, z)
```

After inserting a node in RB Tree, the color of the nodes are fixed using the following algorithm to maintain the balance of the tree.

```
RB_INSERT_FIXUP(T,z)
1. While color [p[z]] = RED
2. Do if p[z] = left [p[p[z]]
3. then y ← right [p[p[z]]]
4. if color [y] = RED
5. then color [p[z]] ← BLACK //Case 1
6. color [y] ← BLACK //Case 1
7. color [p[p[z]]] ← RED //Case 1
8. Z ← p[p[z]] //Case 1
9. else if z = right [p[z]]
10. then z ← p[z] //Case 2
11. LEFT_ROTATE(T,z) //Case 2
12. color [p[z]] ← BLACK //Case 3
13. color [p[z]] ← RED //Case 3
14. RIGHT_ROTATE(T,p[p[z]]) //Case 3
15. else (same as then clause with “right” & “left” exchange)
16. color [root[T]] ← BLACK
```

**Difference between Binary Tree and Binary Search Tree**

Binary Tree | Binary Search Tree |

A non-linear data structure having at most two child nodes. | A node based binary tree where the further subtrees are also binary search tree |

It is unordered. | It is ordered. |

Slower in the process of searching, insertion and deletion. | Faster in the process of searching, insertion and deletion. |

No ordering is there in terms of how the nodes will be arranged. | The elements of the left subtree has values lesser than that of the right sub tree. |

This brings us to the end of the blog on Binary Search Algorithm. We hope that you enjoyed it and were able to learn the concept of Binary Search Algorithm well. If you wish to upskill, you can check out Great Learning Academy’s Free online courses!