You may be a little confused about how a binary search operates. Your doc comment seems to suggest you understand and my cursory look at your code didn't reveal any bugs (but then again, I didn't look too hard). But, this function doesn't really make logical sense.
The purpose of a binary search is to find an item in
O(log(n)) time instead of doing a full scan of a linear datastructure (or at least scanning until you find the item, which worst case is
O(n)). This of course requires the datastructure to already be sorted. Your comment indicates you understand this. But what you end up doing with
pred makes it seem like you confused yourself.
Why? Well if
pred is not a constant time operation, then your binary search is no longer
O(log(n)) (I suspect this is the case, because instead of passing
pred you pass the entire
lst and index
mid). Let's say
O(n). Now the total runtime of
O(n*log(n)), which is significantly worse. In this case, a linear search may be better.
Now, let's just assume
pred is a constant time function. Now the overall runtime remains
O(log(n)), but the return value of
pred still doesn't make sense. Why is this? Well, the list must already be sorted by some ordering. If
pred is constant time, it can only make decisions about the value at
mid (and maybe a few surrounding values), but it can't scan
lst to make decisions. So this means there must be some sort of dependency between the return value of
pred and the sort order of
lst. If there wasn't, your search probably wouldn't work (if say
lst was sorted by ascending value but
pred negated the values before comparing them, it would throw out the wrong half of the list).
So now we assume that
pred is a constant time function that has some dependency on the sort order of
lst. We've shown previously that if either of these doesn't hold, your algorithm is either inefficient or breaks. We now arrive at the last issue.
pred's comparison criteria must be monotone over the sorted list. That is just a fancy way of saying that when
lst is sorted then
pred's comparison criteria must also be sorted. In which case, there isn't a purpose for
pred, since the value of the item itself (which
lst is sorted by this item value) is a proxy for the
pred comparison criteria.
If you didn't follow all of that, don't be too worried. The important point is that you're probably misusing a binary search here. If you want to find the smallest value satisfying a predicate in a list you can just do:
people = [
# (name, age)
('Doe Jane', 52),
('John Doe', 33),
('Jane Doe', 42),
# Min tuple from people by age
youngest_person = min(people, key=lambda p: p)
Note that with
namedtuple this example becomes even more clear:
from collections import namedtuple
Person = namedtuple('Person', 'name age')
people = [
# (name, age)
Person('Doe Jane', 52),
Person('John Doe', 33),
Person('Jane Doe', 42),
youngest_person = min(people, key=lambda p: p.age)
Now you may notice
people is not sorted. You could pass in a sorted list though, but it doesn't make much sense to sort the list, because it's not like you can perform multiple of these operations.
min of a list (that you don't modify) will always be the same. If you change
key then you'd need to resort the list. If you wanted both the min and max, use
max. If performance is of concern (which is unlikely), you could optimize this by having one function that scans over the entire list and keeps track of both the min and max values. If you want to modify the list, then you're probably better off using a heap, which remains sorted with inserts and removals.
Some extraneous issues:
default=None isn't a very common pattern in Python. Sure you see it with
dict.get (and less commonly with
iter), but those are the two places where I can think of. These places have appropriate uses of allowing a default value. For your function a default value doesn't make much sense. Since it returns an index, what use would a "default index" be? I see two options:
return None (and only
None). This simplifies the interface you provide. Allowing for a default value makes it hard for a user of your function to understand what's going on (it's just one more thing to wrap your head around). This way you can explain the function in a sentence: "Returns the minimum or maximum index of the item satisfying a predicate in a sorted list, or None"
- Raise an exception (say
ValueError) if no items satisfy the predicate. This is a very common approach in Python:
KeyError if a key doesn't exist (instead of returning
IndexError if an index is out of bounds (instead of returning
None). This is probably the right choice for you, because a predicate not being satisfied by anything in the list provided is probably an exceptional case that needs to be handled differently (eg. if you were to return
None you couldn't treat it like a number if you wanted to do indexing with it).
Your use of string constants to indicate the mode (
type="min") while common in numpy is a dangerous pattern IMO. You do no
assert type in ('min', 'max'), so what if someone passes in
type="median"? What if they make a typo:
type="mIn"? Both of these appear to lead to behavior you don't want. Worst case (although your code doesn't appear to do this), this could cause an error inside your function. How frustrating would that be for a user of your function to see an error inside your function? This forces them to understand its internals to see if this is a bug in your function or a bug in their use of it. At the least, prefer an
Enum so that if they choose an invalid type they get a
AttributeError (if they tried to do
type=SearchMode.PENULTIMATE, for example).
PEP8 your code. Your spacing needs work. Also wrap to 79 chars, it's really annoying to need to scroll right to read the docs. They're almost surely indented too far.
Instead of doing
p, consider tuple unpacking to give those values more descriptive names:
predicate_satisfied, direction = pred(mid, lst)
You should probably use required kwargs for
default, otherwise, the function call site becomes unclear. Eg. is it
xbinsearch(my_pred, 'min', 1) or
xbinsearch(my_pred, 1, 'min'). Much clearer:
xbinsearch(my_pred, type='min', default=1):
def xbinsearch(pred, lst, *, type='min', default=None):