Table of Contents
The binary search. This simple but important code seems to be the hardest to get right without running into errors. It is used often enough that programmers may build it from memory, but there’s something about it that makes it hard to do so. Ideally, you should have example code to help you out in those times you need it. But in order to truly use things right, understanding is required. This is my attempt at explaining this little ol’ 10 line block of Java.
Think of this in the way that you might search through a dictionary (one of those old school ones made of paper). You open it up randomly, or in this case the middle, and see where you’re at. If the word you’re looking for comes before where you’re at, you grab a big hunk of pages and flip back. But now, you’ve gone too far back, so you take a smaller chunk of pages and flip forward. You continue to do this until you get the page you want. Maybe this process is infinitely more annoying than being able to type a word into a search bar, but it certainly beats out going through the whole dictionary one page at a time. (Unless you’re looking for aardvark.)
Line by Line
Looking at the code above, let’s take things one at a time. If you’re not familiar with Java methods (which are the same as functions in other languages) just leave a question below. I’m willing to take things back as far as anyone would like and explain concepts. This is just something that popped up recently for me. Anyway, the method is taking in, of course, an array, and a key. We’re assuming the array is already sorted, and the key is an integer we’re looking for in the array.
In line 2, we’re setting a lo and hi variable. These will be the index spots for the first and last numbers in the array. As always we should be careful that because arrays start with zero that we note that the index of the last number is one less than the length.
We’ll come back to line 3 at the end of the loop but for now, in line 4 we’re getting the number in the middle of the array. Honestly a.length/2 would have sufficed here because we’re searching from the first to last numbers. But if we wanted to search in a specific spot within the array, this code would allow us to simply change the lo and hi variables.
Now that we’ve got our middle point we can move on to the meat of the problem. We’re saying that if the key (what we’re searching for) is less than the middle number, to change the hi number to the one in the index just below the current mid. This is doing exactly what we talked about in the dictionary example above. We’re cutting our search in half. After this happens, we continue the while loop, reset the middle number based on the new hi, and do the search again.
Line 6 is just the opposite. If the key is higher than the middle number, the new lo becomes the number just above the middle, and we get a new mid by continuing the loop.
Finally, line 7 says that if the key is not less than or greater than the middle (which means the two are equal), our method returns that number, giving us the answer we were looking for. Remember, the current code just acts as an example. The return -1 here is meaningless, and if the key is not in the array, we won’t get a proper answer. But I’ll leave any corrections up to you.
It’s a simple bit of code, but an important one to understand. I know this isn’t the usual sort of article for Liberty.me, but I know there are a lot of coders sneaking around here, and even those learning programming. If there is anything you want a post on, let me know. If you’ve got anything to add, let me know.(I’m especially interested in fun interview questions.) If you’ve got questions, suggestions, or comments, let me know!