I have a sorted, normally distributed list of data that I need to find an element in. Interpolation search is the obvious answer, however, the current approach I’m using is VERY computationally expensive. Basically, for “normal” interpolation search, it’s assumed that the data is uniformly distributed. Then, to get the “starting point”, linear lookup is done, which is essentially plugging in the value that needs to be found into the inverse of the CDF (CDF is cumulative distribution function - for a uniform distribution, the CDF is linear. For interpolation search, the CDF is inverted and the desired value is plugged in to give an approximate address). However, the normal (gaussian) CDF is computationally expensive. Any way to fix that? I was thinking a piecewise linear approach could work - split the distribution into 4 or so “buckets”, and within each bucket, it’s approximately linear, and normal interpolation search can be used.
Also, this is more of an algorithms type question (not directly related to Rust), so should I move it somewhere else? the moment I move this to stackoverflow I’m going to get downvoted into oblivion