What search algorithms are out there for GPUs?

Obviously that’s a broad statement, so let me narrow it down by specifying that I’m thinking on the cross-section lookup problem you typically face when using Monte Carlo codes such as neutron transport/particle transport codes. They have to do a search over hundreds of thousands or millions of values of type double, until they find the indices of the two energy values that are on either side of the energy they want to find; from there it’s lookup and interpolation.

My question is, what algorithms are out there in a more general sense for this kind of thing, and which are preferred for GPUs? Binary search is the obvious first choice, but obviously divergence will be a big issue before very long. I want to know what improvements have been made upon basic binary search for GPUs, or if everyone just uses a completely different kind of algorithm when performing these kinds of searches?

thrust may have some interesting binary search algorithms.

However I wrote my own “naive” parallel binary search that I used for a parallel set intersection, and I was able to be in the ballpark of thrust performance, however that was like 6 years ago. thrust might be worth a look.