This week's book giveaway is in the Mac OS forum. We're giving away four copies of a choice of "Take Control of Upgrading to Yosemite" or "Take Control of Automating Your Mac" and have Joe Kissell on-line! See this thread for details.
In studying the binary search algorithm I have noticed that a while loop is always used. However I wrote the algorithm using a for loop it works fine from what I have tested. I just wanted to know if there is any disadvantage or any other reason a for loop shouldn't be used.
Functionally there's no difference. Any while loop can be written as a for loop and vice versa. It's simply a matter of convention as to when each type is used.
For loops tend to be used when we're saying, "For each item in this group," or "Do it a particular number of times." While loops tend to be used when the end condition is less predictable, or is external, such as "keep going as long as there are more lines to read," or "...until the user enters 'N'".
In your case, I would advise against the for loop because it's a non-standard usage and it makes it a little confusing. When I see the for (int i = 0; i < array.length; i++) part, I assume you're iterating over the array from beginning to end, which is exactly what binary search is intended to avoid. Only after studying it for a moment do I see that you're using it in the sense of "if we count up to this many, then we've examined every element".
Veronica Love wrote:In studying the binary search algorithm I have noticed that a while loop is always used. However I wrote the algorithm using a for loop it works fine from what I have tested. I just wanted to know if there is any disadvantage or any other reason a for loop shouldn't be used.
I think Jeff's covered the main points: your loop looks like its saying "for each element", when what it does is "while I haven't yet found the right index".
But the fact of the matter is that you don't actually need a loop at all.
Java allows 'recursive' methods - that is, a method can call itself - and binary chops are a classic case where it makes a lot of sense to do so.
However, before that: have you tested your method on:
(a) an empty array.
(b) an array with exactly 1 element in it, where the value you supply is NOT it.
The fact is that you are missing a very important check. See if you can work out what it is; otherwise, come back for help.
int middle = (end - start)/2; is also fundamentally flawed. Think about what that equation does (write it out). However, even if you get it right (and it's very easy to get wrong; the original code contained a problem for nearly 10 years), what I said above about your tests still applies.
Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
Joined: Mar 12, 2013
Thanks for the insight guys.
Changed the original code, tests are all passing including the empty array and single value returning false. I see now that the if (array[i] == value line was indeed doing a linear search.