• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Tim Cooke
  • paul wheaton
  • Jeanne Boyarsky
  • Ron McLeod
Sheriffs:
  • Paul Clapham
  • Liutauras Vilda
  • Devaka Cooray
Saloon Keepers:
  • Tim Holloway
  • Roland Mueller
Bartenders:

Binary Search using a for loop

 
Greenhorn
Posts: 8
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.

 
Bartender
Posts: 6109
6
Android IntelliJ IDE Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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".
 
Sheriff
Posts: 17734
302
Mac Android IntelliJ IDE Eclipse IDE Spring Debian Java Ubuntu Linux
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.
 
Bartender
Posts: 10780
71
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • 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.



 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
//Write a program to implement binary search
#include <stdio.h>
void main()
{
int c, first, last, middle, n, search, array[100];

printf("Enter number of elements\n");
scanf("%d", &n);

printf("Enter %d integers\n", n);

for (c = 0; c < n; c++)
scanf("%d", &array[c]);

printf("Enter value to find\n");
scanf("%d", &search);

first = 0;
last = n - 1;
middle = (first+last)/2;

while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
printf("%d found at where %d.\n", search, middle+1);
break;
}
else
last = middle - 1;

middle = (first + last)/2;
}
if (first > last)
printf("not found%d \n", search);


}



 
Marshal
Posts: 80280
432
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Welcome to the Ranch

Would you like briefly to explain the differences between your post and the old code, and between the two languages.
 
So there I was, trapped in the jungle. And at the last minute, I was saved by this tiny ad:
New web page for Paul's Rocket Mass Heaters movies
https://coderanch.com/t/785239/web-page-Paul-Rocket-Mass
reply
    Bookmark Topic Watch Topic
  • New Topic