# Binary Search
**A [[Divide and Conquer#Decrease and conquer|decrease and conquer]] search algorithm for sorted arrays which progressively halves the search space.**
![[BinarySearch.svg|400]]
***Worst-case [[time complexity]]:*** $O(\log n)$
***Worst-case space complexity:*** $O(1)$
> [!Algorithm]
> Compare the middle value to the target.
> - If it is equal to the target, return its index.
> - Else, if it is greater than the target, repeat on the upper half of the array. Otherwise, repeat on the lower half of the array.
The algorithm stops after it *finds the target* or the search space size is reduced to $1$ and the target is *still not found*.
Binary search is the core principle behind a [[binary search tree]].
## Time complexity
In every iteration of the algorithm, the search space is *reduced by half* and thus in the worst case it has $\lfloor \log_{2}n +1\rfloor$ iterations.
Therefore, the worst case time complexity is $O(\log n)$.
## Implementation
```md
**function** binarySearch(*array* A, *size* n, *target* T) **is**
**var** L := 0
**var** R := n - 1
**while** L ≤ R **do**
**var** m := floor((L + R) / 2)
**if** A[m] < T **then**
L := m + 1
**else if** A[m] > T **then**
R := m - 1
**else**
**return** m
**return** error
```
[^1]
In this implementation the algorithm terminates if the target value is found or if `L` is larger than `R`.
### Duplicate elements
If the array has *duplicate elements*, then the above implementation may return the index of any of them.
#### Leftmost duplicate
```md
**function** binarySearchLeftmost(*array* A, *size* n, *target* T) **is**
**var** L := 0
**var** R := n
**while** L < R **do**
**var** m := floor((L + R) / 2)
**if** A[m] < T **then**
L := m + 1
**else**
R := m
**return** L
```
This implementation can also be used for queries of the *rank* and the *predecessor* of the target in the array.
#### Rightmost duplicate
```md
**function** binarySearchRightmost(*array* A, *size* n, *target* T) **is**
**var** L := 0
**var** R := n
**while** L < R **do**
**var** m := floor((L + R) / 2)
**if** A[m] > T **then**
R := m
**else**
L := m + 1
**return** R - 1
```
This implementation can also be used for queries of the *successor* of the target in the array.
[^1]: `floor` refers to the [[Floor and Ceiling Function#^36a512|floor function]].