hi, anyone can please explain this code to me ?
uint32 lower = 0;
uint32 upper = nCheckpoints - 1;
while (upper > lower) {
uint32 center = upper - (upper - lower) / 2; // ceil, avoiding overflow
Checkpoint memory cp = checkpoints[account][center];
if (cp.fromBlock == blockNumber) {
return cp.votes;
} else if (cp.fromBlock < blockNumber) {
lower = center;
} else {
upper = center - 1;
}
}
return checkpoints[account][lower].votes;
Thanks
frangio
September 6, 2022, 8:27pm
2
This is a binary search. There is an explanation of similar code here:
// During the loop, the index of the wanted checkpoint remains in the range [low-1, high).
// With each iteration, either `low` or `high` is moved towards the middle of the range to maintain the invariant.
// - If the middle checkpoint is after `blockNumber`, we look in [low, mid)
// - If the middle checkpoint is before or equal to `blockNumber`, we look in [mid+1, high)
// Once we reach a single value (when low == high), we've found the right checkpoint at the index high-1, if not
// out of bounds (in which case we're looking too far in the past and the result is 0).
Isn't the comment above wrong?
It will avoid overflow, because the subtraction upper - (uper-lower)/2 will never underflow, thanks to the floor division, right?
Skyge
October 25, 2024, 12:12am
5
Hi, welcome to the community!
Yes, the division in Solidity is a floor division, but the comment is right, for example, if upper = 5, lower = 2, then upper - (upper - lower) / 2 => 5 - (5-2)/2 = 5 - 1 = 4, so this is a ceiling value.
Gotcha, so the ceil refers to the entire operation. thanks!
1 Like
