Results 1 to 5 of 5

Thread: Simple boolean question

  1. #1

    Thread Starter
    Junior Member tushardevi's Avatar
    Join Date
    Dec 2017
    Location
    Wales
    Posts
    25

    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

  2. #2
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,988

    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

  3. #3
    Sinecure devotee
    Join Date
    Aug 2013
    Location
    Southern Tier NY
    Posts
    6,582

    Re: Simple boolean question

    Quote Originally Posted by tushardevi View Post
    ...
    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.

  4. #4
    Super Moderator Shaggy Hiker's Avatar
    Join Date
    Aug 2002
    Location
    Idaho
    Posts
    38,988

    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

  5. #5
    Super Moderator jmcilhinney's Avatar
    Join Date
    May 2005
    Location
    Sydney, Australia
    Posts
    110,299

    Re: Simple boolean question

    Quote Originally Posted by Shaggy Hiker View Post
    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
  •  



Click Here to Expand Forum to Full Width