[Tutor] Finding the max value from a dictionary that does not exceed a variable's value.

[Oscar Benjamin]

On 1 February 2016 at 13:29, Steven D'Aprano <steve at pearwood.info> wrote:
>> > although OP's problem doesn't need this, is there a better way achieve
>> > this other than
>> > using a balanced binary search tree.
>>
>> You would need to state all of the requirements for your data
>> structure. If coinvalues is constant then you can use a list and the
>> bisect module:
>>
>> https://docs.python.org/3.5/library/bisect.html
>>
>> That gives O(log(len(coinvalues))) lookup.
>
> There are unlikely to be more than dozen distinct coins. Australia has
> $2, $1, 50¢, 20¢, 10¢, 5¢ coins. Even if you include the obsolete 2¢ and
> 1¢ coins, that's only eight. I believe the US has $1, 50¢ (half dollar),
> 25¢ (quarter), 10¢ (dime), 5¢ (nickel), 1¢ (penny).
>
> You're unlikely to beat a straight linear search with only a few coins
> like this. Binary search has much more overhead. Especially since the
> coin change problem doesn't really require a search: just iterate over
> each coin in turn.

It was acknowledged that "OP's problem doesn't need this" so I assume
the question was to think about it more generally somehow.

--
Oscar