A toy example: suppose we have a big pile of rocks, and we want to find the rock whose mass is closest to the mass of a reference weight (without going over).
A search-in-territory algorithm might use one of those old-school balance-scales to compare masses pairwise. We could pull each rock out of the pile one-by-one, and:
First, compare the rock to the reference weight. If it’s heavier, throw it away and move on to the next rock.
Second, compare it to the best rock found thus far, and replace the best rock with this one if it’s heavier.
At the end, we’ll have chosen the best rock.
Wrong, we have the closest rock iff the closest rock is lighter than the weight.
We’re want the rock that’s closest but not higher, and that’s what we get. We don’t necessarily get the closest rock, but we do get the best one, which is what John said.
Interesting.
Technicality:
Wrong, we have the closest rock iff the closest rock is lighter than the weight.
We’re want the rock that’s closest but not higher, and that’s what we get. We don’t necessarily get the closest rock, but we do get the best one, which is what John said.
Ups, missed that. Thanks.