BUG: Index._searchsorted_monotonic(..., side='right') returns the left side position for monotonic decreasing indexes
State: closed

- [X] closes #17271
- [X] closes #16417
- [X] tests added / passed
- [X] passes `git diff upstream/master -u -- "*.py" | flake8 --diff`
- [X] whatsnew entry

I didn't add a whatsnew entry for the `Index._searchsorted_monotonic` fix, since it looks like past convention has been to not add whatsnew entries for private methods.  Happy to add a whatsnew entry if I'm mistaken though.  I did add a whatsnew entry for the downstream effect on IntervalIndex.

Labels:
name: Indexing
description: Related to indexing on series/frames, not to indexes themselves

Comments:
> since it looks like past convention has been to not add whatsnew entries for private methods.

That is correct.
# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=h1) Report
> Merging [#17272](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/58d872903449b8a29237288ade6227cdb280fe18?src=pr&el=desc) will **decrease** coverage by `50.77%`.
> The diff coverage is `n/a`.

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

```diff
@@             Coverage Diff             @@
##           master   #17272       +/-   ##
===========================================
- Coverage   91.03%   40.25%   -50.78%     
===========================================
  Files         162      162               
  Lines       49567    49540       -27     
===========================================
- Hits        45123    19944    -25179     
- Misses       4444    29596    +25152
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `?` | |
| #single | `40.25% <ø> (-0.05%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9iYXNlLnB5) | `56.35% <ø> (-39.59%)` | :arrow_down: |
| [pandas/tools/hashing.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL3Rvb2xzL2hhc2hpbmcucHk=) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/io/sas/sas\_constants.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2lvL3Nhcy9zYXNfY29uc3RhbnRzLnB5) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/lib.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2xpYi5weQ==) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/parser.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL3BhcnNlci5weQ==) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/tslib.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL3RzbGliLnB5) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/io/json/json.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2lvL2pzb24vanNvbi5weQ==) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/io/formats/style.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2lvL2Zvcm1hdHMvc3R5bGUucHk=) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/types/concat.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL3R5cGVzL2NvbmNhdC5weQ==) | `0% <0%> (-100%)` | :arrow_down: |
| [pandas/io/sas/sas7bdat.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2lvL3Nhcy9zYXM3YmRhdC5weQ==) | `0% <0%> (-90.77%)` | :arrow_down: |
| ... and [112 more](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree-more) | |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/17272?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/17272?src=pr&el=footer). Last update [58d8729...436852e](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

# [Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=h1) Report
> Merging [#17272](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=desc) into [master](https://codecov.io/gh/pandas-dev/pandas/commit/20fee85ede7f2052f855b8f3445cd1ffc17ee0c3?src=pr&el=desc) will **decrease** coverage by `0.01%`.
> The diff coverage is `n/a`.

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

```diff
@@            Coverage Diff             @@
##           master   #17272      +/-   ##
==========================================
- Coverage   91.15%   91.14%   -0.02%     
==========================================
  Files         163      163              
  Lines       49591    49591              
==========================================
- Hits        45207    45201       -6     
- Misses       4384     4390       +6
```

| Flag | Coverage Δ | |
|---|---|---|
| #multiple | `88.93% <ø> (ø)` | :arrow_up: |
| #single | `40.25% <ø> (-0.07%)` | :arrow_down: |

| [Impacted Files](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree) | Coverage Δ | |
|---|---|---|
| [pandas/core/indexes/base.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9iYXNlLnB5) | `96.29% <ø> (ø)` | :arrow_up: |
| [pandas/io/gbq.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2lvL2dicS5weQ==) | `25% <0%> (-58.34%)` | :arrow_down: |
| [pandas/core/frame.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvZnJhbWUucHk=) | `97.72% <0%> (-0.1%)` | :arrow_down: |
| [pandas/core/indexes/datetimes.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9kYXRldGltZXMucHk=) | `95.52% <0%> (+0.09%)` | :arrow_up: |
| [pandas/core/indexes/datetimelike.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9kYXRldGltZWxpa2UucHk=) | `96.88% <0%> (+0.22%)` | :arrow_up: |
| [pandas/core/indexes/range.py](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=tree#diff-cGFuZGFzL2NvcmUvaW5kZXhlcy9yYW5nZS5weQ==) | `92.59% <0%> (+0.3%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/pandas-dev/pandas/pull/17272?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/17272?src=pr&el=footer). Last update [20fee85...41e59d7](https://codecov.io/gh/pandas-dev/pandas/pull/17272?src=pr&el=lastupdated). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments).

Notes regarding the review changes I made:

- Removed some redundant checks from `test_loc_with_scalar` and `test_getitem_with_scalar` in `test_interval.py`, as these checks are now being handled by `test_nonoverlapping_monotonic`  (the index used in the two former tests is nonoverlapping monotonic increasing).

- Added some monotonic decreasing indexes to `setup_method` to various test classes within in order to ensure that monotonic decreasing indexes are fully tested by `common.py/test_searchsorted_monotonic` (and other tests).
   - Had to change ` tm.assert_numpy_array_equal` to `tm.equalContents` in `common.py/test_difference_base`.  Introducing a decreasing sequence led to the test failing with ` tm.assert_numpy_array_equal` due to different sorting of the result and expected answer.  If keeping ` tm.assert_numpy_array_equal` is preferable, the arrays could be sorted prior to using it.
   -  Did not add a monotonic decreasing index to `test_range`, as it currently fails `common.py/test_intersection_base`  due to the issue described in #17296 (will add when I submit a PR for this issue).
> Had to change tm.assert_numpy_array_equal to tm.equalContents in common.py/test_difference_base. Introducing a decreasing sequence led to the test failing with tm.assert_numpy_array_equal due to different sorting of the result and expected answer. If keeping tm.assert_numpy_array_equal is preferable, the arrays could be sorted prior to using it.

yes, pls just sort them if need; we don't use ``tm.equalContents`` (actually should remove that)


> Did not add a monotonic decreasing index to test_range, as it currently fails common.py/test_intersection_base due to the issue described in #17296 (will add when I submit a PR for this issue).

simply add an xfailing test (with the issue number).
Okay, made those additional changes.  ~Any idea why codecov is saying this will decrease coverage by 50%?  I don't think I made any substantial changes that would cause that.  Just a glitch?~

**EDIT:** Nevermind, looks like codecov is fixed.
ping @jreback : made review related updates and did a rebase to resolve merge conflicts
Made the requested changes.  A couple comments:

- Only tested `.searchsorted` for monotonic increasing, since that's the underlying assumption.
- Added an index with repeats to `test_base` to better test `side='right'` for `_searchsorted_monotonic` and `.searchsorted`.
   - Required a modifying `test_get_indexer_consistency` to check uniqueness in one place where uniqueness was assumed.
- Moved the xfail for `test_intersection_base` to only occur for `RangeIndex`, since that's the only type of index that should fail.
ping @jreback : checks are green

Made one small additional change to the `index.is_unique` case.  Since `get_indexer` is implemented slightly differently for `CategoricalIndex` relative to other indexes, they're actually fine even if the values in the index aren't unique, so they fell into the `index.is_unique` case regardless of uniqueness.
ping @jreback : green again after rebasing to address the merge conflict.
thanks @jschendel nice fixes! keep em coming!