ENH: Implement searchsorted for DataFrames

[charlesbluca]

Is your feature request related to a problem?

Pandas currently only supports searchsorted for series:

>>> ser = pd.Series([1, 2, 3])
>>> ser.searchsorted([0, 4])
array([0, 3])

It would be nice if it were also supported for dataframes, returning indices to maintain order in a lexicographically sorted dataframe. This is supported by cuDF:

>>> df = cudf.DataFrame({"a" :[1, 1, 1, 2, 2, 2], "b": list(range(6))})
>>> values = cudf.DataFrame({"a": [1, 1, 2, 2], "b": [1, 2, 4, 6]})
>>> df.searchsorted(values, side="right")
array([2, 3, 5, 6], dtype=int32)

Describe the solution you'd like

The addition of a searchsorted(value, ...) method to pandas.DataFrame, returning the indices to places the elements of values to maintain order in a dataframe lexicographically sorted by all columns.

API breaking implications

None that I can think of.

Describe alternatives you've considered

This could probably be accomplished by converting the dataframe and values to a series of tuples and then using Series.searchsorted, but I imagine there's a more performant way to do this.

Additional context

If this functionality were added, along with a multi-columnar quantiles (#43881), it would enable Dask dataframes to compute sort_values with multiple sort-by columns, using an algorithm roughly similar to that of dask-cudf.

[mzeitlin11]

Is this covered in #42872?

[charlesbluca]

Yes! I will close this in favor of that issue.