# binary search algorithm problem...

This is a discussion on binary search algorithm problem... within the C++ Programming forums, part of the General Programming Boards category; ok for school im literally copy and pasting the binary search algorithm he gave us and apparently went i showed ...

1. ## binary search algorithm problem...

ok for school im literally copy and pasting the binary search algorithm he gave us and apparently went i showed him my flowchart before i coded this program we musta missed something because it always returns a -1 and its due tommorrow and since i copy and pasted the algorithm well just used the already made one i have NO CLUE why its not working since it matches the flowchart just beautiful at least im not noticing an error

anyway why does it always return -1

Code:
```int bin_search(int id[],int elementsize,int user_id)
{
cout <<"BEGIINUIG";
int first = 0;
int last = elementsize -1;
int found = 0;
int mid;
while(first <= last && found == 0)
{
mid = (first + last) / 2;
if(id[mid] == user_id)
found = 1;
else
{
if(id[mid] < user_id)
last = mid - 1;
else
first = mid + 1;
}
}
if(found == 0)
{
cout << "ALMOST THERE";
mid = -1;
}

cout << "ENDING";
return mid;
}```

2. anyway why does it always return -1
Code:
```if(found == 0)
{
cout << "ALMOST THERE";
mid = -1;
}```
BTW work on proper indentation

3. >> BTW work on proper indentation

The forum editor often screws up indentation.

4. put some numbers into your algo and you will see the problem immediately

5. but shouldnt found = 1 if it finds it so then found should never = 0 to assign mid -1? at least thats how i saw it?

and yea the forum editor messed up indention

6. Originally Posted by Daved
>> BTW work on proper indentation

The forum editor often screws up indentation.
Only if you use tabs instead of spaces

7. say u have 0-1000 in a sorted array. try to find 20. follow your code thru and see what happens.

8. >> Only if you use tabs instead of spaces

Don't mean to derail the thread, but while ssjnamek is following the code to see what is wrong, I'll say that the editor messes up spaces as well (at least the WYSIWYG editor).

9. ok i see that it seems to increase instead of chop in half. although i have no clue why its increasing instead of chopping.

well i see why its doing it cause first and last arent changing but by + or - 1 to mid and then just getting readded to mid increasing it. so found is never set to 1 thus returning a negative 1 always.

so now that i have that established i really have NO clue how to fix this none at all. never done binary search before. i get that they cut the search in half each time through. but outside of that never done one before.

so what would i have to do to first and last?

10. In Stoned_Coder's example, first is 0, last is 1000, and user_id is 20. The first time through the loop, first is 0, last is 1000, and mid is (0 + 1000) / 2 which is 500. Since the value in the array is same as the index in this example, id[500] is just 500, which does not equal 20, so you move into the else block.

Now id[mid] is id[500] which is 500 in this case, and user_id is 20, so id[mid] < user_id is false because 500 < 20 is false. That puts us in the inner else statement.

So first = mid + 1 means that first is changing to 500 + 1, or 501. And you will repeat the steps except now you are just looking for 20 in the range 501-1000.

The point of the binary search is to split the list in two and only look into the half that has the value. You are splitting the list in two, but are you continuing with the half that has the value?

11. yes i see that its going in that range so i need it in range 0-499. so i swap the first and last.

and yea now it returns a normal number 0

ok thanks for helping me figure out the madness lol

and daved i have to ask anytime you post are you always offline cause its like you instantly sign off or have constant ghosting? lol

12. It says I'm invisible next to my posts. I probably turned off the show online option when I registered. Or maybe I am just that quick.

13. lol could be but if i catch it saying online ill be sure to printscreen it and sell it on ebay as a rare find lol