Generalisation of Binary Search
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 lst[mid] to pred you pass the entire lst and index mid). Let's say pred is O(n). Now the total runtime of xbinsearch is 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: min(lst, key=pred).

For example:

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[1])


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 min and 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: dicts raise KeyError if a key doesn't exist (instead of returning None), lists raise 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[0] and p[1], consider tuple unpacking to give those values more descriptive names:

predicate_satisfied, direction = pred(mid, lst)


You should probably use required kwargs for type and 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):
    # ...