API: remove ordered requirement in Categorical.searchsorted
State: closed

- [x] closes #21667
- [x] tests added / passed
- [x] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [x] whatsnew entry

``searchsorted`` is mainly a tool to find value locations in a sorted array. As such it doesn't make sense to restrict it to not work with unordered categoricals. For example, doing searchsorted on ordered, but unsorted arrays gives wrong result, so orderedness is a relatively irrelevant thing to check for in searchsorted.

The current solution to first convert to a ordered Categorical is inelegant and requires setting up different code paths depending on the situation:

```python
if categorical.ordered:
    val = c.searchsorted(key)
else:
    val = c.as_ordered().searchsorted(key)
```

I've also added to the doc string of searchsorted to make clear that sortedness is required for a correct result (this is not an issue that is limited to categoricals, but all Arrays)

Labels:
name: API Design
name: Categorical
description: Categorical Data Type

Comments:
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21686?src=pr&el=h1) Report
> :exclamation: No coverage uploaded for pull request base (`master@bbfd4ba`). [Click here to learn what that means](https://docs.codecov.io/docs/error-reference#section-missing-base-commit).
> The diff coverage is `100%`.

[![Impacted file tree graph](https://codecov.io/gh/pandas-dev/pandas/pull/21686/graphs/tree.svg?width=650&token=eZ4WkYLtcO&height=150&src=pr)](https://codecov.io/gh/pandas-dev/pandas/pull/21686?src=pr&el=tree)

```diff
@@            Coverage Diff            @@
##             master   #21686   +/-   ##
=========================================
  Coverage          ?   91.77%           
=========================================
  Files             ?      174           
  Lines             ?    50704           
  Branches          ?        0           
=========================================
  Hits              ?    46535           
  Misses            ?     4169           
  Partials          ?        0
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `90.37% <100%> (?)` | |
| #single | `41.81% <0%> (?)` | |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/21686?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/21686/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYmFzZS5weQ==) | `98.19% <ø> (ø)` | |
| [pandas/core/arrays/categorical.py](https://codecov.io/gh/pandas-dev/pandas/pull/21686/diff?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvYXJyYXlzL2NhdGVnb3JpY2FsLnB5) | `95.91% <100%> (ø)` | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21686?src=pr&el=continue).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/21686?src=pr&el=footer). Last update [bbfd4ba...a21dc4d](https://codecov.io/gh/pandas-dev/pandas/pull/21686?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

@topper-123 needs rebase
this needs evaluation
I don’t think we want to allow this
you can easily get incorrect results
I discuss some of my points in favor of this in #21667:

In ``searchsorted`` its already not possible to guard against incorrect result. Also letting this into the code base (.searchsorted on .codes) would just mimic existing ``sort_values`` behaviour (sort on .code):

```python
>>> c = pd.Categorical(['a', 'a', 'b', 'b', 'c'], categories=pd.Index(['b', 'a', 'c']))
>>> c.sort_values()
[b, b, a, a, c]
Categories (3, object): [b, a, c]
``` 

We can perhaps continue the discussion in #21667.

I agree with @topper-123: it is indeed easy to get wrong results with searchsorted, but that is a general issue with that function, and not necessarily specific to `Categorical.searchsorted`. 
`searchsorted` requires the values to be sorted, but `ordered=True` is not necessary to sort a Categorical, so IMO should also not be needed for searchsorted
``.sort_values()`` is a red-herring here, we are simply lexographically sorting which is expected. Its too easy to make mistakes with ``.searchsorted`` here. A doc warning is not great. I would leave this like it is.
> .sort_values() is a red-herring here, we are simply lexographically sorting which is expected.

Yes, and this sorting will mean that the codes are sorted, so I don't understand why the above is a reason to not do this?
> Yes, and this sorting will mean that the codes are sorted, so I don't understand why the above is a reason to not do this?

I think its pretty unituitive to sort by codes in an unordered categorical, we should actually disallow ``.sort_values()`` as well (or maybe allow it but sort by the lexographic categories themselves). 

e.g. we should raise just like we do for min/max.
```
In [1]: c = pd.Categorical(list('AABCD'))

In [2]: c.min()
TypeError: Categorical is not ordered for operation min
you can use .as_ordered() to change the Categorical to an ordered one


In [3]: c.sort_values()
Out[3]: 
[A, A, B, C, D]
Categories (4, object): [A, B, C, D]

```
Being able to sort is very useful, we discussed this before, so I am -1 on removing that ability (but if you want further discuss this, I would open a new issue).

Note that, in the majority of the use cases for unordered categoricals, sorting by the codes or sorting lexicographically will be identical, exactly because we do sort the categories lexicographically on creation. 
So only when passing the categories manually and not setting `ordered=True`, this might be different.
I agree with @jorisvandenbossche.

IMO It is beneficial to be able find locations of groups of values unordered values, so ``lhs, rhs = c.searchssorted(val1, side='left'), c.searchsorted(val1, side='right')`` should be possible, also for unordered categoricals, because this the fastest way to look up locations (much faster than ``c[c==val1]``.

To do the above, unordered categoricals need to have ``sort_values``, ``is_monotonic*`` and ``searchsorted``...
Looks like this stalled. In the meantime, this could use a rebase..
Closing as stale. Ping if you'd like to continue
I would actually very much like to continue this, but was under the impression it wasn't going to get in. If you'll open it, I'll push a rebase.
will have another look
if you can merge master and remove the 0.24.0 docs. pls ping.
I'll look into this over the weekend.
@topper-123 can you merge master and we'll have another look see
I've rebased.
@topper-123 can you rebase
@topper-123 still active?
Yeah, I've rebased. The PR is quite old, so fixed some strange git issues by just merging the commits into one.
Taking another look at this again. Read through history but I think I am also on the side of not doing this. Understood on the point about consistency with other aspects of the API but I personally find this confusing, and a doc note isn't a great guard against that.

So I think @jreback and I are -1 here, @topper-123 and @jorisvandenbossche are +1. Still accurate?

This is oldest PR in queue so would like to decide how to move forward so it isn't in limbo forever
@WillAyd can you explain what exactly you find confusing? 
Note that the doc note is added to the generic `searchsorted` docstring, as this point is true for all dtypes (you always need to ensure yourself that the values are sorted when calling this method). There is nothing categorical specific about this gotcha with `searchsorted`. 

The only thing with Categoricals is that it can be a bit harder to know if your values are sorted or not. But, you *can* sort an unordered categorical with `sort_values`, you can check if they sorted with `is_monotonic`. 
And for `searchsorted` to work, the only requirement is sortedness, which an unordered categorical still has.
Agree with everything @jorisvandenbossche said.

I would like to add that ``searchsorted`` is used to get fast lookups, so for performance sensitive work, having ``searchsorted`` is necessary.
I find  what is quoted in the docstring to be confusing:

```python
If the values are not monotonically sorted, wrong locations
   may be returned:

>>> x = pd.Series([2, 1, 3])
>>> x.searchsorted(1)
0  # wrong result, correct would be 1
```

I understand that this affects non-Categorical right now, but IMO this should be raising for non-monotonic instead of returning surprising results. I don't think expanding that coverage to non-sorted Categorical moves us in the right direction
> I understand that this affects non-Categorical right now, but IMO this should be raising for non-monotonic instead of returning surprising results

Then maybe we could split those two issues? Let's open a separate issue to discuss raising for non-monotonic in general, and move forward with this PR making searchsorted available consistently across dtypes?


Any more thoughts here?
I guess this is fine, though IMHO this is scope creep for ordered categoricals. by-definition unordered ones are not ordered (well they *have* an order, but it is not exposed to the users per se). that being said, I guess for perf reasons this is desireable.
I've rebased.
Thanks @topper-123 for the PR and @jorisvandenbossche for input