PERF: fix slow s.loc[[0]]

Fixes #9126

```
-------------------------------------------------------------------------------
Test name                                    | head[ms] | base[ms] |  ratio   |
-------------------------------------------------------------------------------
series_loc_list_like                         |   0.2840 | 125.0146 |   0.0023 |
series_loc_array                             |   0.9947 | 125.5813 |   0.0079 |
series_loc_scalar                            |   0.0430 |   0.0424 |   1.0150 |
series_loc_slice                             |   0.0647 |   0.0606 |   1.0668 |
-------------------------------------------------------------------------------
Test name                                    | head[ms] | base[ms] |  ratio   |
-------------------------------------------------------------------------------
```

Whee!

I also wrote this fix for `IntervalIndex` (#8707); this change pulls it out separately. I believe it changes the complexity of the lookup check from O(n*m) for length n index and length m key to O(n+m).