The most suitable algorithm for finding the price?

Question

JavaScript

Hello!

Tell me which algorithm to use or how best to do it. I have an object/associative array (language dependent) with prices (prices with cents) as keys and name as text, something like: [1=>'name1', 2=>'name2'... 55233=>'name555']. Prices will be sorted. There will be about 50k items in total. At the entrance, I receive a price, for example 5.23, and I need to find among all the keys, either the key = 5.23, or the closest one down.

I think to solve this using a binary search, maybe there is something more efficient? If it is important, then I will solve the problem on js.

Answer 1

To do a binary search, you need an array of objects with prices and names. Something like

[1=>{cost:1, name:"name1"} .... 117=>{cost:55233, name:"name555"}]

(I'm not sure what I described correctly in js).
But, in theory, all normal languages ​​​​can do something like lower_bound for associative arrays. This is the function that needs to be called. And then choose the best of the current and previous or next element (depending on how lower_bound works in your language).
You can look for some js libraries with a normal associative array that can do this.
Will also work for the logarithm.

Answer 2

Maxim , it's simple.
Always keep an up-to-date interval-amount distribution curve. Create and update it as new data becomes available. This is called iterative data segmentation.
Perform a downward search immediately from the desired segment, shifting to the left by one interval: search only in it.
The more data in one segment, the more intervals and create. This will reduce the time to find the value you need.