# Binary Search

## Algorithms and Data Structures

A binary search employs a divide and conquer strategy to find the position of a target value in a sorted list. A binary search is also known as a half-interval search, logarithmic search, or binary chop.

For binary search to work the **list must be sorted** (sorting is a discussion for another time).

Given a sorted list from which we want to find the number `35`

:

Begin by splitting the list into two halves, disregarding the half that is less than, or greater than, `35`

:

Split the remaining half into two — again disregarding the half that is less than, or greater than, `35`

:

Repeating again finds `35`

at position `5`

in the list:

## Complexity

🔔 Complexity is considered in terms of worst case.

### Time

Notes | |
---|---|

Θ(log n) |

### Space

Notes | |
---|---|

Θ(1) | Requires three pointers to the list elements, regardless of list size |

## An implementation

```
// TypeScript
export interface IBinarySearchResult {
position: number;
}
export function binarySearch<T>(values: T[] = [], target: T): IBinarySearchResult {
let low = 0;
let high = values.length - 1;
while (low <= high) {
const middle = Math.floor((low + high) / 2);
if (values[middle] === target) {
return {
position: middle,
};
}
if (target < values[middle]) {
high = middle - 1;
} else {
low = middle + 1;
}
}
return {
position: -1,
};
}
```

### A recursive alternative

```
// TypeScript
export function binarySearchRecursive<T>(
values: T[] = [],
target: T,
low: number = 0,
high: number = values.length - 1): IBinarySearchResult {
if (low <= high) {
const middle = Math.floor((low + high) / 2);
if (values[middle] === target) {
return {
position: middle,
};
} else if (target < values[middle]) {
return binarySearchRecursive(values, target, low, middle - 1);
} else {
return binarySearchRecursive(values, target, middle + 1, high);
}
}
return {
position: -1,
};
}
```