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?
I understand it as "ceil division", but the division is a floor division isn't it?

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