File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Binary Search using a for loop

 
Veronica Love
Greenhorn
Posts: 8
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Posts: 6109
6
Android IntelliJ IDE Java
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Pie
Posts: 6529
21
Java Linux Mac Scala Spring
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Winston Gutkowski
Bartender
Pie
Posts: 9465
49
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Veronica Love
Greenhorn
Posts: 8
  • 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.



 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic