# Mastering Binary Search Algorithm [The Ultimate Guide] This is the most complete guide on Binary Search Algorithm.

In this in-depth guide, you’ll learn:

1. What is Binary Search?
2. How does Binary Search work?
3. Binary Search Algorithm
4. Visual Representation of Binary Search Algorithm
5. Flowchart of the Binary search algorithm
6. Two different approach to implement the binary search algorithm
• Iterative Approach
• Recursive Approach

So, Let’s get started!

## What is Binary Search?

Let’s try to understand about binary search from its name itself.

So, as the name indicates, Binary Search consists of two words. Right?

The first word i.e., Binary means two or something having two parts.

As, In the world of computer, Zero and One (i.e., 0 & 1) collectively called binary because it consists of two entity 0 and 1.

And,

Search means, to look over or inspect by exploring all the possible places to find or discover something: such as; to find a particular data item from a data set or from a list of data items, like array.

So, after combining these two words i.e., Binary and Search, we can say, It is an approach to find the position of a target (specific) value by dividing a list of data items (generally arrays) into two halves.

And, then the item (target value) is compared with the middle element of the list.

If the match is found, the location of the middle element is returned.

Otherwise, we search into either of the halves depending upon the result produced through the match.

If the target value is less than the middle element, the search is performed on the left half of the list.

And, If the target value is greater than the middle element, the search is performed on the right half of the list.

This process is repeated until the target value is found or determined to be absent or the search space is exhausted.

? Note: Binary search can be applied only on a sorted array or list of items. So, If the elements are not sorted already, we need to sort them first.

## How does Binary Search work?

Let’s understand the working of binary search, step-by-step:

Variables we are using here:

1. start: Start index pointing to the first element of the array.
2. end: End index pointing to the last element of the array.
3. n: Total number of elements in the array. It also represents the size or length of the array.
4. key: The target/key element to be search.
5. mid: Middle index, which initially points to the middle element of the array.

The following algorithm is used to search an element in an array using binary search algorithm:

### Binary Search Algorithm:

• Step 01: Start
• Step 02: Set the start index to the first element of the array, i.e., `start` `=` `0`
• Step 03: Set the end index to the last element of the array, i.e., `end` `=` `n - 1`
• Step 04: Repeat Step `05` to Step `15` until start is less than or equal to the end index.
• Step 05: Set middle index to `start + (end - start) / 2`.
• Step 06: If `arr[mid] == key`
• Step 07: Return `mid`
• Step 08: Go to Step `18`.
• Step 09: [End of If ]
• Step 10: else if `arr[mid] < key`
• Step 11: Set `start = mid + 1`
• Step 12: [End of Else-If ]
• Step 13: else
• Step 14: Set `end = mid - 1`
• Step 15: [End of Else ]
• Setp 16: [End of step `04` loop ]
• Step 17: `return` `-1` (If no match is found, or the search space is exhausted or if the start index exceeds the end index)
• Step 18: Stop.

Now, before going into the detailed expalantion of the above algorithm, let’s first understand how to calculate the middle index efficiently.

You can also calculate the middle index by using this formula: i.e., `mid = (start + end) / 2`.

But, instead of using the above formula why am I using the formula: `mid = start + (end - start) / 2`. Right?

Answer: It’s only because, Let’s consider a scenario where the values of start and the end index are very large (nearly to the range of Integer data type).

For `unsigned __int32` the Range of Values is `0` to `231 – 1`.

So, after adding these two values (i.e., start + end) may exceed the range of integers.

And, even if start and end are within the range, the sum overflows to a negative value for large arrays, and the value stays negative when divided by two. This causes an array index out of bounds with uncertain results.

So, to overcome from this problem, we are first subtracting the start index from the end index after that dividing this value by two and then adding it to the start index.

Now, let’s jump into the detailed explanation of the above algorithm.

Explanation of the above Algorithm:

In the above algorithm, `step 2` and `step 3` are self explanatory. Right?… As we are just creating two variables and initializing it with `0` and `n - 1` respectively.

And, `step 4` is basically the beginning of the while loop block which will run until the start index is less than or equal to the end index.

After that, inside the while block in the `step 5`, we are setting the value of the middle index which is equal to `start + (end - start) / 2`.

In `step 6`, we are comparing the value at the middle index with the target value, If the match is found, `step 7` will execute and the location of the middle element is returned, after that the flow of execution goes to the `step 18` and the If block will end in `step 9`.

In `step 10`, If the above `If` block does not satisfies the condition, and the value at the middle index is less than the target value, then we set the value of start as `start = mid + 1`.

Why we are setting the start as `mid + 1`? Right?

It’s only because, As we already know that the binary search will work only when the array is sorted. Right?

So, If the value at the middle index is less than the target value then it simply means, the target value will be on the right part of the array.

And, that’s why we are setting the `start` index to `mid + 1`.

So that, the half part can be ignored for the next iteration of the while loop.

After that, In the `step 12`, the else-if block will terminate.

Now, In `step 13`, if the `else-if` condition is not true then `else` block will execute.

And, In the `else` block, we are setting the end index to `mid - 1`.

The reason is very simple, if the `else-if` condition will not true then it simply means, the `arr[mid]` value is greater than target value.

So, there is no need to search in the right part of the array, and that’s why we are neglecting the right part.

Which means, If we set the `end` index to `mid - 1`, then we are automatically neglecting the right part of the array and the search will taken on the left part of the array.

After that, `step 15` and `step 16` are the end of else block and the while loop block respectively.

And, at the last step, In `step 17`, We are returning `-1`.

This step will execute only when If no match is found, or the search space is exhausted or if the start index exceeds the end index.

That’s it for all the steps of the above algorithm.

### Flowchart of the Binary search algorithm:

Now, let’s come to the implementation part of the binary search algorithm.

Basically, there are two different ways or approach to implement the binary search algorithm:

1. Iterative approach
2. Recursive approach

Let’s understand the above two approaches one-by-one:

### Implementation of Iterative approach:

```// writing a program in C++ for binary search in an array

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int n, int key)
{

int start = 0;   // starting index of the array
int end = n - 1;    // ending index of the array

while(start <= end)
{
int mid = start + (end - start) / 2;      // middle index of the array

if(arr[mid] == key)
return mid;

else if(arr[mid] < key)
start = mid + 1;

else
end = mid - 1;
}
return -1;
}

int main()
{
int arr[ ] = { 2, 5, 7, 8, 9, 13};

int n = sizeof(arr) / sizeof(arr);

int key = 9;

int result = binarySearch(arr, n, key);

: cout << "Element is present at index: "  << result;

return 0;

};

```

If you compile and run the above program, it will produce the following result:

Output:

```Element is present at index: 4

```

### Implementation of Recursive approach:

```// writing a program in C++ to implement recursive Binary Search

#include <bits/stdc++.h>
using namespace std;

int binarySearch(int arr[], int start, int end, int key)
{
if (end >= start) {
int mid = start + (end - start) / 2;

if (arr[mid] == key)
return mid;

if (arr[mid] > key)
return binarySearch(arr, start, mid - 1, key);

return binarySearch(arr, mid + 1, end, key);
}
return -1;
}

int main()
{
int arr[] = { 1, 7, 13, 16, 35 };
int key = 10;
int n = sizeof(arr) / sizeof(arr);
int result = binarySearch(arr, 0, n - 1, key);
(result == -1)
? cout << "Element is not present in the array"
: cout << "Element is present at index " << result;
return 0;
};

```

If you compile and run the above program, it will produce the following result:

Output:

```Element is not present in the array

```

## Conclusion:

In this article, you learned all the things you need to know about “Binary Serach”, you also became familiar with the algorithm and flowchart of the Binary Search Algorithm.

So,

I really hope that you liked my article and got a lot of value from it. 