# Ace The Binary Search

## What is binary search?

Binary search begins by comparing the middle element of the list with the target element. If the target value matches the middle element, its position in the list is returned. If it does not match, the list is divided into two halves.

## Time and Space Complexities :

• Best Time Complexity: O(1)
• Average Time Complexity: O(log n)
• Worst Time Complexity: O(log n)
• Best Space Complexity: O(1)-0

## Pseudo code for binary search:

`BinarySearch(array, target):{    left = lowestBound(array)    right = highestBound(array)    WHILE (left <= right)    {        middle = (left + right) / 2        if(target = array[middle])            RETURN middle        else if(target < array[middle])           right = middle - 1        else           left = middle + 1    }    RETURN -1}`

## Example:

Consider the following list of 5 numbers: 21, 22, 23, 24, 25. We need to find whether number 25 is present in the list or not.

## Beyond Sorted Array Binary Search

Binary search obviously works on searching for elements in a sorted array. But if you think about the reason why it works is because the array itself is monotonic ( either increasing or decreasing ). So, if you are a particular position, you can make a definite call whether the answer lies in the left part of the position or the right part of it.

--

--