Generalisation of Binary Search

Question

I wrote a function to implement a generalised version of binary search that can find the minimum or maximum index in a given sorted list that satisfies a provided predicate.

My Code

def xbinsearch(pred, lst, type = "min", default = None):
    """
        * Finds the minimum or maximum index of a sorted list such that the value at that index satisfies a given predicate.

        *   Params:
            *   `pred`: Predicate function. 
                *   Params:
                    *   `idx`: The index of the value to be tested.
                    *   `lst`: The list to search for said value in.
                *   Return: An ordered pair of the form `(x, y)`.
                    *   `x`: Boolean indicates whether or not `lst[idx]` satisfies the predicate.
                    *   `y`: `-1`, `1` or `None`.
                        *   `-1` indicates that if `lst[idx]` does not satisfy the predicate, then all values below `lst[idx]` also do not satisfy the predicate.
                        *   `1` indicates that if `lst[idx]` does satisfy the predicate, then all values above `lst[idx]` also do not satisfy the predicate.
                        *   `None` is given with `True` for the first index of the ordered pair.
                        *   It is used to determine which "half" to discard in the binary search.
    """
    low, hi, best = 0, len(lst)-1, default
    while low <= hi:
        mid = (low+hi)//2
        p = pred(mid, lst)
        if p[0]:    #The current element satisfies the given predicate.
            if type == "min":
                if best == default or lst[mid] < lst[best]: best = mid
                hi = mid-1
            elif type == "max":
                if best == default or lst[mid] > lst[best]: best = mid
                low = mid+1
        elif p[1] == 1:     #For all `x` > `lst[mid]` not `P(x)`.
            hi = mid - 1
        elif p[1] == -1:    #For all `x` < `lst[mid]` not `P(x)`.
            low = mid + 1
    return best

---

Sample Use Case

Problem Element equals its index

Given a sorted array of distinct integers, write a function index_equals_value that returns the lowest index for which array[index] == index.
Return-1` if there is no such index.
Your algorithm should be very performant.

[input] array of integers ( with 0-based nonnegative indexing )
[output] integer

Examples:

input: [-8,0,2,5]  
output: 2 # since array[2] == 2  

input: [-1,0,3,6]  
output: -1 # since no index in array satisfies array[index] == index    

Random Tests Constraints:

Array length: 200 000

Amount of tests: 1 000

Time limit: 1.5 s

My Code

def identity(idx, lst):
    tpl, val = [None, None], lst[idx]
    tpl[0] = val == idx 
    if val < idx:   tpl[1] = -1
    elif val > idx: tpl[1] = 1
    return tuple(tpl)


def xbinsearch(pred, lst, type = "min", default = None):
    low, hi, best = 0, len(lst)-1, default
    while low <= hi:
        mid = (low+hi)//2
        p = pred(mid, lst)
        if p[0]:    #The current element satisfies the given predicate.
            if type == "min":
                if best == default or lst[mid] < lst[best]: best = mid
                hi = mid-1
            elif type == "max":
                if best == default or lst[mid] > lst[best]: best = mid
                low = mid+1
        elif p[1] == 1:     #For all `x` > `lst[mid]` not `P(x)`.
            hi = mid - 1
        elif p[1] == -1:    #For all `x` < `lst[mid]` not `P(x)`.
            low = mid + 1
    return best

def index_equals_value(lst):
    return xbinsearch(identity, lst, default = -1)

Answer 1

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:

1. 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"
2. 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):
    # ...