WIP: searchsorted implementation
State: closed

closes #6712

we've decided to simply return `self.values.searchsorted`, since that's what was happening before, and because dealing with non-monotonic indices is a PITA and yields marginal benefit when you can just use `s.iloc[s.searchsorted(...)]`
- [x] ~~`timedelta64` tests~~ #8464 
- [x] ~~more edge case testing~~ #8464 
- [x] ~~how should non-monotonic indexes be handled (currently raising a `ValueError`)?~~
- [x] ~~`datetime64` (and probably `timedelta64`) coercion needs work~~
- [x] ~~`side` argument testing~~ #8464 
- [x] documentation
  - [x] docstring
  - [x] add to api.rst
  - [x] add to basics.rst


Labels:
name: Enhancement
name: API Design
name: Algos
description: Non-arithmetic algos: value_counts, factorize, sorting, isin, clip, shift, diff

Comments:
@jreback is there a convenient way to convert something datelike (timedelta or datetime) to the numpy representation but leave it alone if it's doesn't smell like one of those things?

their is a needs_i8_conversion in core/common (returns boolean)

how this coming?

still workiing on it

but coming along

status?

i'll push to 0.15.0

@cpcloud after Index-not sub-class ndarray is merged (still a little while yet), I think this will be quite straightfoward to modify

@jreback i'll finish this implementation before that's finished :)

np, either was it should be moved to `core/base.py` I will just swap out mine for yours.

ok i can move it

nvm i isee

@jreback i think we should disallow out of bounds `searchsorted`, what do you think? i don't think special casing the monotonic integer case is worth it

@cpcloud not sure I understand what is out-of-bounds searching, you mean raise if you didn't find it at all?

sorry for not being clear. for example

```
In [6]: x = randn(5)

In [7]: x
Out[7]: array([-1.5827, -0.2143, -0.0106, -1.232 , -0.4901])

In [8]: np.sort(x).searchsorted(10)
Out[8]: 5
```

I mean easy enough to check (e.g. if `len(x) == x.searchsorted(value)` then its not found). What would you do, raise `IndexError`? hmm

but technically its returning the index to insert (which is correct).

do you have a usecase?

The use case is that a monotonic `Int64Index` is easily broken:

```
In [31]: s = Series([3, 1, 2, 0, -1])

In [32]: s
Out[32]:
0    3
1    1
2    2
3    0
4   -1
dtype: int64

In [33]: s.order()
Out[33]:
4   -1
3    0
1    1
2    2
0    3
dtype: int64
```

What would `s.order().searchsorted(4)` do here?

And this obviously doesn't make sense for object or irregular time series indices

hmm. I thought this was just a pass thru to `s.values` in effect (accomodating different key types, e.g. `Timestamp` and such.

But you want to return the `.index` I guess, and since it is missing its an error then, right? So raise `IndexError`

FYI as an aside, if you _knew_ the series was ordered, e.g. you could `i = Index(s.values); i.is_monotonic`, then I bet `i.get_loc` is faster.

nvm I think `searchsorted` requires it to be sorted (actually, so I *_would_ do the index check and raise if its not). (though I think reverse sort is ok too)

you also need to know that whatever's being passed into `i.get_loc` is `in i`, right?

no, it will raise if its not found (KeyError). 

`searchsorted` just tells you where it _would_ put something, so if you pass in something `not in i` then it should still be a valid result

i'm only suggesting that going out of bounds be disallowed

ok, I think raising `IndexError` would be ok then 

going back and looking at wes' book shows that `searchsorted` didn't ever return the index, it pretty much just did `self.values.searchsorted` ... should we really be returning the `Index`?

i don't mean to drag this out so much but there's just all sorts of oddities and special cases simply to return an index... this isn't exactly intuitive:

```
In [29]: s
Out[29]:
4   -1
3    0
1    1
2    2
0    3
dtype: int64

In [30]: s.searchsorted(0.5)
Out[30]: 1
```

it only returns the index by it was a ndarray method. I think you _should_ return the index actually. Otherwise you can simply use `s.values.searchsorted`. Then again, on an actual `Index` it returns an indexer I think, (like `get_indexer`)

ok, so then just make it like `s.values.searchsorted` much easier

(and user can always do: `s.iloc[s.searchsorted(...)]` if they really want. \

FYI I don't even know what you would actually use this for... 

ok, just to beat a dead zorse, i guess what i'm saying is that forcing `searchsorted` to be label-based doesn't seem worth the trouble and basically saying "this will always be position based" is easier to remember than trying figure out what my above example is doing (tho not that hard, but i would find that surprising if i was a pandas noob)

FWIW i've used this to search for things to avoid boolean indexing, with mixed results ... it works, but not that much faster