Inconsistent handling of empty slices with non-monotonic indexes
These two should probably behave the same

`df1` has a non-monotonic datetimeindex, and we slice with values that don't fall in the index.
`df2` has a non-monotonic index of strings, which we slice values outside the index.

```python
In [9]: import pandas as pd
   ...:
   ...: df1 = pd.DataFrame({"A": [1, 2, 3]},
   ...:                    index=[pd.Timestamp('2017'),
   ...:                           pd.Timestamp('2019'),
   ...:                           pd.Timestamp('2018')])
   ...: df2 = pd.DataFrame({"A": [1, 2, 3]},
   ...:                    index=['a', 'c', 'b'])
   ...:

In [10]: df1.loc['2020':'2022']
Out[10]:
Empty DataFrame
Columns: [A]
Index: []

In [11]: df2.loc['d':'e']
---------------------------------------------------------------------------
ValueError                                Traceback (most recent call last)
~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexes/base.py in get_slice_bound(self, label, side, kind)
   3664             try:
-> 3665                 return self._searchsorted_monotonic(label, side)
   3666             except ValueError:

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexes/base.py in _searchsorted_monotonic(self, label, side)
   3623
-> 3624         raise ValueError('index must be monotonic increasing or decreasing')
   3625

ValueError: index must be monotonic increasing or decreasing

During handling of the above exception, another exception occurred:

KeyError                                  Traceback (most recent call last)
<ipython-input-11-e86df68316ba> in <module>()
----> 1 df2.loc['d':'e']

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexing.py in __getitem__(self, key)
   1367
   1368             maybe_callable = com._apply_if_callable(key, self.obj)
-> 1369             return self._getitem_axis(maybe_callable, axis=axis)
   1370
   1371     def _is_scalar_access(self, key):

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexing.py in _getitem_axis(self, key, axis)
   1575         if isinstance(key, slice):
   1576             self._has_valid_type(key, axis)
-> 1577             return self._get_slice_axis(key, axis=axis)
   1578         elif is_bool_indexer(key):
   1579             return self._getbool_axis(key, axis=axis)

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexing.py in _get_slice_axis(self, slice_obj, axis)
   1400         labels = obj._get_axis(axis)
   1401         indexer = labels.slice_indexer(slice_obj.start, slice_obj.stop,
-> 1402                                        slice_obj.step, kind=self.name)
   1403
   1404         if isinstance(indexer, slice):

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexes/base.py in slice_indexer(self, start, end, step, kind)
   3529         """
   3530         start_slice, end_slice = self.slice_locs(start, end, step=step,
-> 3531                                                  kind=kind)
   3532
   3533         # return a slice

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexes/base.py in slice_locs(self, start, end, step, kind)
   3730         start_slice = None
   3731         if start is not None:
-> 3732             start_slice = self.get_slice_bound(start, 'left', kind)
   3733         if start_slice is None:
   3734             start_slice = 0

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexes/base.py in get_slice_bound(self, label, side, kind)
   3666             except ValueError:
   3667                 # raise the original KeyError
-> 3668                 raise err
   3669
   3670         if isinstance(slc, np.ndarray):

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexes/base.py in get_slice_bound(self, label, side, kind)
   3660         # we need to look up the label
   3661         try:
-> 3662             slc = self._get_loc_only_exact_matches(label)
   3663         except KeyError as err:
   3664             try:

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexes/base.py in _get_loc_only_exact_matches(self, key)
   3629         get_slice_bound.
   3630         """
-> 3631         return self.get_loc(key)
   3632
   3633     def get_slice_bound(self, label, side, kind):

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/core/indexes/base.py in get_loc(self, key, method, tolerance)
   2529                 return self._engine.get_loc(key)
   2530             except KeyError:
-> 2531                 return self._engine.get_loc(self._maybe_cast_indexer(key))
   2532
   2533         indexer = self.get_indexer([key], method=method, tolerance=tolerance)

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/_libs/index.pyx in pandas._libs.index.IndexEngine.get_loc()
    137             util.set_value_at(arr, loc, value)
    138
--> 139     cpdef get_loc(self, object val):
    140         if is_definitely_invalid_key(val):
    141             raise TypeError("'{val}' is an invalid key".format(val=val))

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/_libs/index.pyx in pandas._libs.index.IndexEngine.get_loc()
    159
    160         try:
--> 161             return self.mapping.get_item(val)
    162         except (TypeError, ValueError):
    163             raise KeyError(val)

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/_libs/hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()
   1263                                        sizeof(uint32_t)) # flags
   1264
-> 1265     cpdef get_item(self, object val):
   1266         cdef khiter_t k
   1267         if val != val or val is None:

~/Envs/pandas-dev/lib/python3.6/site-packages/pandas/pandas/_libs/hashtable_class_helper.pxi in pandas._libs.hashtable.PyObjectHashTable.get_item()
   1271             return self.table.vals[k]
   1272         else:
-> 1273             raise KeyError(val)
   1274
   1275     cpdef set_item(self, object key, Py_ssize_t val):

KeyError: 'd'
```

cc @jreback @shughes-uk