4 ms·
> 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
by 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 agoIt 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.