1. ## Simple boolean question

Hello everyone!

I have made a pseducode for a binary search :

BinarySearch()
Set first = 1
Set last = n
set mid = 0
Repeat
Found = false
mid = (first+last)/2
if WantedKey = Key[mid] then
found = true
if WantedKey < Key[mid] then
last = mid - 1
else
first = mid + 1
end if

Here the variable "found" is initialised to false. And its value only will change to true when the item is found in the list. The last line reads : unitl not found. Does this mean "until found = true" or does it mean "until found = false", considering that I initialised the variable to false. Also, NOT(false) will make TRUE.
Am I right?

Thank You

2. ## Re: Simple boolean question

I don't like using Found as a Boolean. How about making Found an integer? It would start at -1, but if the thing is found, then it is set to the index of the thing. This way, the method won't just say whether or not the item is found, it will return an index at which it is found, which will often be the next thing you'd want to know. Might as well do both at once.

You've also got an issue with your logic:

If WantedKey < key[mid] Then
first = mid-1
Else WantedKy > key[mid] Then
last = mid + 1
End if

What you had may have just been a typo, but I wanted to be sure. If the item is below the midline, then set the range to be the item below the midline down to the old last value. If the item is above the midline, then set the range to be the old first value down to the item above the midline.

3. ## Re: Simple boolean question

Originally Posted by tushardevi
...
Here the variable "found" is initialised to false. And its value only will change to true when the item is found in the list. The last line reads : unitl not found. Does this mean "until found = true" or does it mean "until found = false", considering that I initialised the variable to false. Also, NOT(false) will make TRUE.
Am I right?

Thank You
I'm not sure what you want to confirm is right, since there are several statements there.
Until will loop until the expression is true. Another way of saying it, it will loop while the expression is false.
Not, inverts a boolean expression.
So....
'Not False' is True, as you say, so you will exit loop as soon as you haven't found what you're looking for.

So, if you found the value on the first try, you will loop back and look again until you don't find it and then will exit the loop.

If you don't find it on your first shot, you have succeeded in not finding it so will exit the loop. You're looping

As for lowering the End point if the value is less than the mid value, or raising the Start point if the value is after the mid value that seems correct to me, I'm not sure what SH had an issue with. Of course, the assumption is that the value is in the list. A real search would have to account for the first or last value being the same after adjusting indicating you didn't find the item at all.

4. ## Re: Simple boolean question

Yeah, I read part of it wrong. Therefore, I think what I had a problem with was the formatting, not the contents. I still prefer to use an integer over a Boolean, though.

5. ## Re: Simple boolean question

Originally Posted by Shaggy Hiker
I still prefer to use an integer over a Boolean, though.
It depends what the point is. The String class has both Contains and IndexOf methods for a reason. If all you care about is whether something exists then an Integer is of no use to you except as something that you can convert to a Boolean by comparing it to -1. Why not get a Boolean to begin with if that's what you actually want?

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•

Featured