On Mon, Feb 01, 2016 at 12:47:02PM +0000, Oscar Benjamin wrote: > On 31 January 2016 at 05:50, srinivas devaki <mr.eightnotei...@gmail.com> > wrote: > > On Sun, Jan 31, 2016 at 3:54 AM, Danny Yoo <d...@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 _______________________________________________ Tutor maillist - Tutor@python.org To unsubscribe or change subscription options: https://mail.python.org/mailman/listinfo/tutor