Basic Computer Science > Lists and Arrays

**The
Binary Search Algorithm**

(Original
Essay - Printable Version)

All right, so you've read about sorting
algorithms, and now you've got a sorted array. Just having a sorted
array, however, doesn't do anything for you unless you are going to Assume you have a sorted array. Now, when you search for that item, what
you really want to do is Now, let's say that the elements of your sorted array are records of employees, sorted by the employee's 3-digit company ID number (this is a small company, so the number is - we can hope - unique to each employee). Now, we want to see if an employee with a certain ID number - 243, for instance - exists. Let's call that number the target number. There are a variety of algorithms to search a sorted array, but we shall examine only two of them. One is extremely simple, and the other one is still relatively easy, but it is greatly more efficient. The Of course, if the target number were really big, then we'd have to compare
it to almost every single element in the array before deciding whether
or not it is in the array, and that's The linear search method works well for arrays with which you can only
access the elements of the array in order that they come; this kind of
array is called a For normal arrays, however, there is a more efficient method. This algorithm
relies upon the fact that you can access any element of the array without
having to go through all of the elements before it; this ability is called
Let's say our ordered array has 100 employees recorded in it. Since we
can access any array element we want, and since the array elements are
in order, wouldn't it be more efficient to start searching in the Now, we're down to one section of the array. We could search this section
with the linear method...or we could just treat it as another array and
start from the middle again. Now, we can do this over and over until we
either find an element that matches the target number, or we're down to
a section with only one element in it that doesn't match the target number.
So, we've got the results we wanted, and the algorithm is much faster
than just searching from one end. This method is called the For the people knowledgeable about What does this mean in non-mathematical terms? Well, if you have a sorted
array of one thousand elements, using the first searching method, you
might search all of the elements, making up to 1000 comparisons in the
worst case. With the second method, however, you will make The way you implement the binary search algorithm is really quite simple. You need two variables: a low variable (usually named lo) and a high variable (usually named hi), which keep track of the beginning and the end of the section of the array that you are looking at. Initially, lo will store the index value of the first element of the array (in C++, that is normally 0), and hi will store the index value of the last element of the array (in C++, that would be n-1, where n is the number of elements). You need to find the middle of the section. The index for the middle element is basically (hi - lo)/2 + lo rounded off to the nearest integer in some manner. If t (the target number) is less than the middle element, then reset hi to equal that middle element's index. If t is greater than the middle element, then reset lo to equal the middle element's index instead. That means that in the next round, we will only look at the elements with index numbers greater than lo and less than hi. In this way, you will eventually narrow down on where the target number should be in the array. This handy little algorithm has been used everywhere, and it has even
been modified to be used in a Chess playing algorithm called |

Original Essay's URL:
http://www.aihorizon.com/essays/basiccs/lists/binsearch.htm |