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

[Steven D'Aprano]

On Mon, Feb 01, 2016 at 12:47:02PM +0000, Oscar Benjamin wrote:
> On 31 January 2016 at 05:50, srinivas devaki <mr.eightnoteight at gmail.com> wrote:
> > On Sun, Jan 31, 2016 at 3:54 AM, Danny Yoo <dyoo at hashcollision.org> wrote:
> >> ---
> >> I want to take the max value in the dictionary 'coinvalues'  that is the
> >> same as or lower than the variable 'change'.  I have no idea how to search
> >> through the 'coinvalues' dictionary and find the value that is highest but
> >> does not exceed the value held in the variable 'change'.
> >> ---
> >
> > 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.


-- 
Steve