š§

# Binary Search

- List
*must be sorted* - Divide and conquer
- Eliminates half the elements every time
- Maximum steps --> $log_2 n$
- As input doubles, the maximum number of steps increases by one

## Complexity

Time | Space |
---|---|

$O(log(n))$ | |

Split the search space by two on every iteration |

## Process

- Start by searching in the middle
- If what you are looking for is
*smaller*than what you find in the middle, restrict search up to the middle - If what you are looking for is
*bigger*than what you find in the middle, restrict search space from middle on - Repeat until you find what you're looking for or your search space has nothing in it

## Implementations

### JavaScript

```
function binarySearch(target, sortedArray) {
// Start the search space with the entire array
let lowIndex = 0;
let highIndex = sortedArray.length - 1;
// While the search space has elements in it...
while (lowIndex <= highIndex) {
// Grab the middle, acounting for a min (lowIndex)
const middleIndex = lowIndex + Math.floor((highIndex - lowIndex) / 2);
const guess = sortedArray[middleIndex];
// Target found!
if (guess === target) {
return middleIndex;
}
if (guess < target) {
// Middle is less than target
// Adjust search space to second half of current search space
lowIndex = middleIndex + 1;
} else {
// Middle is greater than target
// Adjust search space to first half of current space
highIndex = middleIndex - 1;
}
}
return -1;
}
```

### Python

```
def binary_search(target, sortedArray):
lowIndex = 0
highIndex = len(list) - 1
while lowIndex <= highIndex:
middleIndex = (lowIndex + highIndex) / 2
guess = sortedArray[middleIndex]
if guess == target:
return middleIndex
if guess < target:
lowIndex = middleIndex + 1
else:
highIndex = middleIndex - 1
return None
```