Why can't binary search be used in an unsorted array?


1 Answers

Jon Moody Profile
Jon Moody answered

Imagine you are trying to find a house on a really long street with 1000 houses. This is the future and we have mastered the ability to teleport. All you have is the street address but you don't know which houses have addresses. They might be numbered 1, 5, 9, 19, 25, 28, 37 and so on. Cities leave these gaps on purpose to have addresses to use if any new houses are constructed later.

The easiest way to find the house quickly would be to teleport to the halfway point on the street. You could look at the address of the house you are at. If the house you want is a bigger number, then you know it must be one of the houses farther down the street. But if the house you are looking for is a smaller number is must be in the other direction.

By teleporting to the halfway point you've cut the number of houses to search in half. The first time you teleported halfway to the 500th house in the street. But you can cut the houses in half again by repeating the process. If the house number you want is bigger, you teleport to the 750th house. If the house number you want is smaller, you teleport to the 250th house. You check again and quickly begin to narrow down where the house must be.

Since every teleport cuts the number of houses in half, you are guaranteed to find the house you want in 11 teleports or less. This is much faster than checking all 1000 houses one at a time. This is exactly how a binary search works. The computer goes to the halfway point of a sorted list and then checks to see if what it want is closer to the beginning or the end. It repeats the process, each time cutting how much needs to be searched in half.

This assumes the list is sorted. Lets go back to the house analogy. Let's say all the houses on the street were numbered randomly (54, 1009, 2, 4006, 57, 186, 17, ...) then going to the halfway point wouldn't help. When you go to the 500th house, you have no way to know if the house you want is to the right or left because they are not in order. The only way to find the right house is to check them one by one.

Binary searches are used to an extent by people all the time. When we look up people in a telephone book, we use a similar process of flipping close to where we think it might be then flipping a few pages forward or back until we find the right phone number. If the names in the phone book were out of order or just put in randomly, it would be practically impossible to ever find what you are looking for.

Answer Question