Search Algorithms

You know that a topic is interesting to you when you get excited about it even though the lecture you learn about it in isn't the best. Most of the lectures in the Stanford Programming Methodology Java course were pretty good and easy to follow for me but one taught by the teaching assistant was more difficult to follow. No offense is intended to that teaching assistant, I'm sure with more experience he's a better teacher now. Thankfully, as I said, the topic grabbed me anyway.

Seek and You Will Find

We learned about arrays, creating them and valuing them. Then we had to write something to reverse the order of the items in an array. But what about searching them for a value? That was one thing I was always curious about when creating queries in Access or writing things in OmniScript to search for database records. What was going on under the hood to make searching faster? Was writing something one way going to make for a quicker, more efficient search or not? Therefore I was quite interested in learning about search algorithms.

Linear Searches

Linear searches are the most basic kind of searches. To search an array for a value with a linear search is to look at each value in the array, one at a time, in sequential order, until the search value is found or the end of the array is reached. Naturally this takes some time. Computers are very fast, but if the array is very large, this still takes some time. If an array has 100,000 values, each one might have to be looked at.  I realized that there must be some more efficient ways to search, and there are.

Binary Searches

As long as an array's values are sorted in order, you can do a binary search. With a binary search, the value in the middle of the array is looked at first, and if that value in the middle is lower than the value being searched for, then the whole first half of the array can be eliminated as the value being searched for must be in the second half of the array, if it exists. The opposite is true if the value in the middle is higher than the value being searched for. So if the array has 100,000 values, with the first search, 50,000 values are eliminated and no longer need to be looked at.

Next, the middle value of the remaining values is looked at and the process is repeated. If needed, it is repeated again and again, each time cutting the number of values that need to be looked in half. This, of course, makes the search much more efficient and greatly reduces the time needed to perform the search.

A binary search is much like we humans would search a dictionary or phone book. We don't look at every entry, we jump in at a point and decide which way we need to turn to find what we're looking for and we repeat that until we find our entry.

So Which to Use?

Because binary searches can be so much quicker, one might think they are always preferred. But again, in order to do a binary search, the array has to already be sorted. So if an array is already sorted, then a binary search is the obvious choice. But what if the array isn't sorted? Of course you could sort the array so that you can do a binary search. But of course that's going to take time. So for each case you have to decide what's going to be faster. If you are going to need to do a lot of searches on this array then it's probably best to spend the time to sort it as each binary search you do will save a lot of time. If on the other hand, the search only needs to be performed once or a couple of times, then just running the linear search might be the fastest thing.

i++