4
\$\begingroup\$

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)
\$\endgroup\$
  • \$\begingroup\$ Could you give a use case for this code? What would the parameters be? I'm having a hard time comming up with a predicate function that fits this case. \$\endgroup\$ – Ralf Feb 20 at 17:26
  • \$\begingroup\$ (I hope the doc string is accurate with Finds the minimum or maximum index (not value as in the introductory sentence).) \$\endgroup\$ – greybeard Feb 20 at 18:15
  • \$\begingroup\$ @greybeard I changed from value to index as I found the latter more useful, but forgot to update the question itself (as opposed to just the code). \$\endgroup\$ – Tobi Alafin Feb 21 at 10:39
4
\$\begingroup\$

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):
    # ...
\$\endgroup\$
  • 1
    \$\begingroup\$ Nice answer, I'd just add a last note on pred's return value: there is no need for it to be a couple, since the second element alone can be used to infer the first one (if -1 or 1 it was false, otherwise it was true), so better return -1, 0, or 1 as usual for a comparison function. Or use bisect with a key function. \$\endgroup\$ – 409_Conflict Feb 21 at 8:38
  • \$\begingroup\$ pred is constant time. I pass the entire list, because for the problem that made me design this generalisation of binary search the predicate was: lst[idx] == idx. pred needs to know at what index the element in the list occurs. It is generally a constant time function. I will add a sample use case to my question. \$\endgroup\$ – Tobi Alafin Feb 21 at 10:43
  • \$\begingroup\$ I have added the sample use case. I did not actually create the generalised binary search to solve that problem (I solved it first, then upon reflecting on the code I used to solve it, came up with the generalised version). \$\endgroup\$ – Tobi Alafin Feb 21 at 10:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.