# Binary Search

```
function binarySearch(arr, seekNum) {
let startIndex = 0;
let endIndex = arr.length - 1;
while (startIndex <= endIndex) {
const middle = startIndex + Math.floor((endIndex - startIndex) / 2);
if (seekNum === arr[middle]) {
return middle;
}
if (arr[middle] < seekNum) {
startIndex = middle + 1;
} else {
endIndex = middle - 1;
}
}
return -1
}
```

## How it works

- split array in half
- determine if the thing you are looking for is in the left half or right half
- make the winning half the new base array that you are searching for
- repeat 1-3 until base array can not be split any further
- if item remaining is the search key, then give it’s position. If it isn’t, then the item doesn’t exist in the array

## info

- keep splitting the array in half until you are left with the result you were looking for
- array must be sorted for binary search to work
- recursive in nature, but is more efficient as a loop
- when duplicates exist, the index of the matching item will not consistently be the first/last/etc duplicate item. Just comes down to where the closest slice hits
- there are variations of binary search that find the rightmost/leftmost duplicate element

- binary search can also be adapted to approximation searches