Linear and Binary Search Algorithms

Computers are particularly good at sifting through lots of data. But somebody needs to tell the computer how to do it. We need to give the computer instructions that it can follow. It is kind of like following a recipe for baking a cake. A recipe tells you all of the things you need to do and what order to do them in. In computer science terminology, we call the recipe an algorithm.

Even though computers are pretty fast these days, we need to find good algorithms to avoid making the computer do more work than it has to. We will use the example of searching through a list to show you two different algorithms.


Linear Search

Suppose we want to write an algorithm to get the computer to search through a list of numbers (like a list of airline flight numbers). The list is ordered from the smallest to the biggest. The easiest way to find our number is to start at the beginning and compare our number (which we will call the target) to each number in the list. If we reach our target, then we are done. This method of searching is called Linear Searching.

Here is the algorithm:

  1. Start with the first item in the list.
  2. Compare the current item to the target
  3. If the current value matches the target then we declare victory and stop.
  4. If the current value is less than the target then set the current item to be the next item and repeat from 2.
Now, how do we tell the computer our algorithm? We need to give instructions to the computer in a language (code) it understands. If you would like to look at the code for Linear Search written in the Java programming language, click here. When you understand the symbols in the language, the algorithm looks pretty similar to the code.

If we have to look at every item in the list to find out if it matches our target, it could take a while. Can we create an algorithm that doesn't need to look at every item?

Binary Search

Think about how you look for a name in the phone book. You open it up somewhere in the middle and then see if you need to go forward or backward. We need to give the computer more precise instructions than this so we will tell it to divide the list exactly in half and compare the middle item to our target. If the middle item is smaller than our target, then we can look at the top half of the list. If it is bigger than our target, we will tell the computer to look in the bottom half of the list. We call this kind of search Binary Searching because we always divide the number of items we will search in half.

Here is the algorithm:

  1. Set the list to be the whole list
  2. Find the middle value of the list
  3. If the middle value is equal to the target then we declare victory and stop.
  4. If the middle item is less than the target, then we set the new list to be the upper half of the old list and we repeat from step 2 using the new list.
  5. If the middle value is greater than the target, then we set the new list to be the bottom half of the list, and we repeat from step 2 with the new list.
The Java code for Binary Searching can be found here.
Karen Reid
Last modified: Thu Mar 2 17:43:33 EST 2000