-
Feb 22nd, 2018, 12:58 PM
#1
Thread Starter
Junior Member
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
until not found
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
-
Feb 22nd, 2018, 01:31 PM
#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.
My usual boring signature: Nothing
-
Feb 22nd, 2018, 02:00 PM
#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
until it is not found. (Until Not Found)
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.
Last edited by passel; Feb 22nd, 2018 at 02:04 PM.
-
Feb 22nd, 2018, 03:02 PM
#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.
My usual boring signature: Nothing
-
Feb 22nd, 2018, 07:24 PM
#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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|