5 ms·

You are correct, however most binary search algorithms wouldn't need negative numbers.

IncRnd 4y ago
It is, however, the exact case shown in the linked article. "Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number."
- roflyear 4y ago
  You don't need a negative number to solve that fyi.
  - anonymoushn 4y ago
    If the correct number is -300 you might
    - roflyear 4y ago
      No, because in the context of a binary search you should be able to map everything to a positive integer. So if your question is "find the midpoint, so I can start searching there" your "midpoint" is not going to be a negative number in the context of binary search. I think in the unfortunate example question the binary search is from -1000 to +1000, but the question is not about binary search, it is about finding the midpoint between two numbers.
      - IncRnd 4y ago
        > No, because in the context of a binary search you should be able to map everything to a positive integer. So if your question is "find the midpoint, so I can start searching there" your "midpoint" is not going to be a negative number in the context of binary search. That's not true. Binary search doesn't map everything to a positive integer. You are incorrectly looking at the index offset, but the issue is determining the midpoint between two signed numbers.
        roflyear 4y ago
        It is being pedantic, but the issue is in the context of binary search: Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number. With each guess, I tell you whether your guess is correct, smaller or larger than my number. A binary search algorithm tries to find a value in an interval by repeating finding the midpoint, using smaller and smaller intervals. You might start with 0, then use either -500 or 500 and so forth. You don't need negative numbers to do this.... you can easily do it with only positive numbers.

It is, however, the exact case shown in the linked article. "Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number."

roflyear 4y ago
You don't need a negative number to solve that fyi.
- anonymoushn 4y ago
  If the correct number is -300 you might
  - roflyear 4y ago
    No, because in the context of a binary search you should be able to map everything to a positive integer. So if your question is "find the midpoint, so I can start searching there" your "midpoint" is not going to be a negative number in the context of binary search. I think in the unfortunate example question the binary search is from -1000 to +1000, but the question is not about binary search, it is about finding the midpoint between two numbers.
    - IncRnd 4y ago
      > No, because in the context of a binary search you should be able to map everything to a positive integer. So if your question is "find the midpoint, so I can start searching there" your "midpoint" is not going to be a negative number in the context of binary search. That's not true. Binary search doesn't map everything to a positive integer. You are incorrectly looking at the index offset, but the issue is determining the midpoint between two signed numbers.
      - roflyear 4y ago
        It is being pedantic, but the issue is in the context of binary search: Let us say that I ask you to find the number I am thinking about between -1000 and 1000, by repeatedly guessing a number. With each guess, I tell you whether your guess is correct, smaller or larger than my number. A binary search algorithm tries to find a value in an interval by repeating finding the midpoint, using smaller and smaller intervals. You might start with 0, then use either -500 or 500 and so forth. You don't need negative numbers to do this.... you can easily do it with only positive numbers.