aspose file tools*
The moose likes Beginning Java and the fly likes Binary Search using a for loop Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Binary Search using a for loop" Watch "Binary Search using a for loop" New topic
Author

Binary Search using a for loop

Veronica Love
Greenhorn

Joined: Mar 12, 2013
Posts: 8
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.

Jeff Verdegan
Bartender

Joined: Jan 03, 2004
Posts: 6109
    
    6

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".
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 5019
    
    8

Your implementation is not a binary search. Your first check

is wrong. You should always be checking array[middle] if you're performing a binary search. Your code ends up doing a linear search, despite the operations you perform on middle, start, and end.


Junilu - [How to Ask Questions] [How to Answer Questions]
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8250
    
  23

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.

Winston

PS: Doh-h-h!
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
Veronica Love
Greenhorn

Joined: Mar 12, 2013
Posts: 8
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.



 
 
subject: Binary Search using a for loop