# Binary Search

Binary Search operates on a contiguous sequence with a specified left and right index. This is called the Search Space. Binary Search maintains the left, right, and middle indices of the search space and compares the search target to the middle value of the collection.

## **Time and Space Complexity:**

**Runtime:** `O(log n)`&#x20;

Because Binary Search operates by applying a condition to the value in the middle of our search space and thus cutting the search space in half, in the worse case, we will have to make O(log n) comparisons, where n is the number of elements in our collection.

> Why **`log n`**?
>
> * **Binary search is performed by dividing the existing array in half.**
> * **So every time we complete one iteration the size reduced to half of the existing part.**
> * **First `N` become `N/2`, then it become `N/4` and go on till it find the element or size become 1.**
> * **The maximum no of iterations is `log N` (base 2).**

**Space Complexity:** `O(1)` -- Constant Space

## **Different problems of binary search:**

{% content-ref url="binary-search/template-i/search-in-a-sorted-rotated-array" %}
[search-in-a-sorted-rotated-array](https://soumyajit4419.gitbook.io/ds-algo/binary-search/template-i/search-in-a-sorted-rotated-array)
{% endcontent-ref %}

{% content-ref url="binary-search/template-ii/find-minimum-in-rotated-sorted-array" %}
[find-minimum-in-rotated-sorted-array](https://soumyajit4419.gitbook.io/ds-algo/binary-search/template-ii/find-minimum-in-rotated-sorted-array)
{% endcontent-ref %}

{% content-ref url="binary-search/template-iii/3.find-peak-element" %}
[3.find-peak-element](https://soumyajit4419.gitbook.io/ds-algo/binary-search/template-iii/3.find-peak-element)
{% endcontent-ref %}

{% content-ref url="binary-search/template-iii/4.-find-first-and-last-position-of-element-in-sorted-array" %}
[4.-find-first-and-last-position-of-element-in-sorted-array](https://soumyajit4419.gitbook.io/ds-algo/binary-search/template-iii/4.-find-first-and-last-position-of-element-in-sorted-array)
{% endcontent-ref %}

{% content-ref url="binary-search/template-i/5.sqrt-x" %}
[5.sqrt-x](https://soumyajit4419.gitbook.io/ds-algo/binary-search/template-i/5.sqrt-x)
{% endcontent-ref %}
