# Binary Search Analysis

Binary search is a search algorithm used to find a specific element in a sorted collection of elements. It works by repeatedly dividing the collection in half and comparing the target element with the middle element of the current sub-collection. This allows the algorithm to quickly narrow down the search space and find the target element with fewer comparisons than linear search.

## How Algorithm of Binary Search works?

Here is how binary search works in detail:

1. Start by dividing the collection in half and examining the middle element.
2. Compare the target element with the middle element of the current sub-collection.
3. If the target element is equal to the middle element, return the index of the middle element.
4. If the target element is less than the middle element, repeat the search on the left half of the sub-collection.
5. If the target element is greater than the middle element, repeat the search on the right half of the sub-collection.
6. Repeat steps 2-5 until the target element is found or the search space is exhausted.

Binary search is a very efficient algorithm, with a time complexity of O(log n), where n is the number of elements in the collection. This means that the search time grows logarithmically with the size of the collection, making it much faster than linear search for large collections.

Here is the pseudocode for binary search:

``````binary_search(collection, target):
low = 0
high = length of collection - 1

while low <= high:
mid = (low + high) / 2

if collection[mid] == target:
return mid
else if collection[mid] < target:
low = mid + 1
else:
high = mid - 1

return -1
``````

In this pseudocode, the `collection` parameter represents the sorted collection of elements that we want to search, while the `target` parameter represents the element that we want to find within the collection. The algorithm works by setting two pointers, `low` and `high`, to the beginning and end of the collection, respectively. It then enters a loop that continues until the `low` pointer is greater than the `high` pointer, which means the target element was not found. Within the loop, the algorithm calculates the `mid` index by taking the average of the `low` and `high` pointers, and then compares the `mid` element with the `target` element. If a match is found, the algorithm returns the index of the `mid` element. If the `mid` element is less than the `target` element, the algorithm updates the `low` pointer to `mid + 1` and continues the search on the right half of the collection. If the `mid` element is greater than the `target` element, the algorithm updates the `high` pointer to `mid - 1` and continues the search on the left half of the collection.

Note that the binary search algorithm assumes that the collection is sorted in ascending order. If the collection is not sorted, the algorithm will not work correctly.

### Example Code

Here’s an example of a C++ program that performs binary search:

```#include <iostream>
using namespace std;

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

int main()
{
int arr[] = {3, 5, 8, 12, 18, 20, 25, 30};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 18;
int result = binarySearch(arr, n, x);
if (result == -1)
else
cout << "Element found at index: " << result;
return 0;
}
```

The above program will output:

``Element found at index: 4``

## Complexity Analysis of Binary Search

The time complexity of binary search is O(log n), where n is the size of the input array. This means that the running time of the algorithm grows logarithmically with the size of the input.

The reason for this is that binary search repeatedly divides the search space in half, eliminating half of the remaining possibilities at each step. This results in a much faster search time compared to linear search, which has a worst-case time complexity of O(n), where n is the size of the input array.

The space complexity of binary search is O(1), which means that the algorithm requires a constant amount of memory to run, regardless of the size of the input array. This is because binary search only needs to store a few variables to keep track of the search space and the target element.

In general, binary search is a very efficient algorithm for searching sorted arrays, and can be used to search for a specific element or to find the position of an element where it can be inserted to maintain sorted order. However, binary search requires that the input array be sorted beforehand, which can be a disadvantage if the array needs to be frequently updated or modified.

## When is the Binary Search algorithm used?

Binary search is commonly used when searching for a specific element in a sorted array or collection. It is an efficient algorithm for searching large arrays, as it has a time complexity of O(log n), where n is the size of the array.

Binary search can also be used to find the position where a new element can be inserted into a sorted array while maintaining the sorted order. This can be useful in situations where a new element needs to be added to a sorted list or array.

However, it is important to note that binary search requires that the array be sorted beforehand. If the array is frequently updated or modified, it may not be the most efficient algorithm to use. Additionally, if the array is very small, the overhead of performing binary search may outweigh its benefits compared to simpler search algorithms like linear search.

1. Binary search is a very efficient algorithm for searching sorted arrays or collections, as it has a time complexity of O(log n), where n is the size of the array.
2. It is a divide-and-conquer algorithm that reduces the search space in half with each iteration, making it very fast for large arrays.
3. Binary search can be used to find the position where a new element can be inserted into a sorted array while maintaining the sorted order.
4. It is a simple algorithm that can be easily implemented in most programming languages.