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
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,[&](inti)->constint{returni*i>=1000;});
auto it=lower_bound(kr.begin(),kr.end(),1);
printf("%d\n",distance(kr.begin(),it));
}
Recommended Posts