Say you had to determine whether 15 was in the array below, *without* using a built-in method. How would you do it?

```
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
```

One way would be to go through each value in the array, check if it was equal to 15, and return true if so. Something like this:

```
for i in 0...array.length do
if array[i] == search
return true
end
end
```

Easy enough. But linear search has a worst-case time complexity of O(N), meaning in a worst-case scenario (say we were looking for 21, or a value that doesn't exist like 10) we would have to compare every single element.

Not too bad for an array of 11 items, but not great if it was 100M values long. That's 100M potential comparisons!

Enter Binary Search. So powerful, it will find any value in a 100M length array in a maximum of 27 comparisons. How come?

The key feature of our array is that it is *already sorted*. If we pick the middle value, we know that everything to the left is less or equal, and everything to the right is greater or equal.

```
array = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21]
# middle value is 11
```

If we're searching for 15, we can make one comparison with the midpoint 11. 15 is greater than 11, so we can instantly cut our search in half as there is no need to look at the left half of the array. We can then start our new search at 13 and find a new midpoint.

Binary search uses the fact the array is sorted to cut our search list in half every time we make a comparison. That's huge!

## Pseudocode

- Set a search start and search finish variable
- While our search area is valid (i.e. start is less than or equal to our finish)
- Set the midpoint index halfway between start and finish
- Compare the value at that midpoint index with our search value
- If they're equal, great! We can return the midpoint
- If the midpoint value is higher than search, then we set our finish index to be the index before our midpoint
- If the midpoint value is lower than search, then we set our start index to be the value after our midpoint
- If the value isn't there, our search area will eventually become invalid, and we'll return false

## Iterative Ruby Code

Solving this iteratively, the code then looks something like this:

```
def binarySearch(array, search)
start = 0
finish = (array.length) - 1
while start <= finish
midpoint = (start + finish) / 2
if array[midpoint] == search
return midpoint
elsif array[midpoint] > search
finish = midpoint - 1
elsif array[midpoint] < search
start = midpoint + 1
end
end
return false
end
```

## Recursive Ruby Code

We can also write this recursively, using the same logic. I think it's a bit cleaner, but it does use more memory and we'll need to pass in our start/finish variables as arguments:

```
def binarySearchRecursive(array, search, start, finish)
if finish < start
return false
end
midpoint = (start + finish) / 2
if array[midpoint] == search
return midpoint
elsif array[midpoint] > search
binarySearchRecursive(array, search, start, midpoint - 1)
elsif array[midpoint] < search
binarySearchRecursive(array, search, midpoint + 1, finish)
end
end
```

And that's binary search! Hope you found this useful and/or interesting, and it saves you some time next time you need to find a needle in a 100M strong haystack...

## Top comments (0)