Binary search in Python / C++ #Python

You can use bisect module to perform binary search in Python.
But unfortunately, unlike Ruby's bsearch, you cannot pass lambda (or key) to the function.

However, you can pass a fantastic class to make a special comparison.

This example will compute math.ceil(math.sqrt(1000)). You can modify f() to any custom stuff.

#!/usr/bin/python

class KeyRange(object):
    def __init__(self, lo, hi, key):
        self.lo = lo
        self.hi = hi
        self.key = key
    def __len__(self):
        return self.hi-self.lo
    def __getitem__(self, k):
        return self.key(k)

def f(n):
    return n**2>=1000
import bisect
print(bisect.bisect_left(KeyRange(0,1000,f),1))

PS

Well, this looks like what Guido loves, indeed...

Acknowledgements

https://gist.github.com/ericremoreynolds/2d80300dabc70eebc790

C++

Recentry I updated cpp_range (https://qiita.com/cielavenir/items/94c9abbb7767bd57607b) to enable KeyRange. You can find some fun on it, although using partition_point looks better.

Usage is like this:

#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;

int main(){
    auto kr=makeKeyRange(0,1000,[&](int i)->const int{return i*i>=1000;});
    auto it=lower_bound(kr.begin(),kr.end(),1);
    printf("%d\n",distance(kr.begin(),it));
}