Binary search in Python / C ++

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

Binary search in Python / C ++
Binary search in Python
Binary search in Python (binary search)
Algorithm in Python (ABC 146 C Binary Search
Algorithm in Python (binary search)
Write a binary search in Python
Binary search (python2.7) memo
[Python] Binary search ABC155D
Linear search in Python
Binary search with python
Binary search with Python3
C API in Python 3
Extend python in C ++ (Boost.NumPy)
C language ALDS1_4_B Binary Search
Search for strings in Python
Algorithm in Python (breadth-first search, bfs)
Save the binary file in Python
ABC166 in Python A ~ C problem
Create a binary file in Python
Algorithm in Python (depth-first search, dfs)
Solve ABC036 A ~ C in Python
Write a depth-first search in Python
How to wrap C in Python
[C language algorithm] Binary search tree
Solve ABC037 A ~ C in Python
Write C unit tests in Python
Depth-first search using stack in Python
Quadtree in Python --2
Python in optimization
CURL in python
Metaprogramming in Python
Solve ABC175 A, B, C in Python
Python 3.3 in Anaconda
Geocoding in python
SendKeys in Python
Algorithm learned with Python 10th: Binary search
Meta-analysis in Python
Unittest in python
Try working with binary data in Python
Implement FIR filters in Python and C
Search and play YouTube videos in Python
Epoch in Python
Sudoku in Python
DCI in Python
visualize binary search
quicksort in python
nCr in python
Write O_SYNC file in C and Python
N-Gram in Python
Programming in python
python C ++ notes
Plink in Python
Constant in python
ABC146C (binary search)
python, openFrameworks (c ++)
Lifegame in Python.
FizzBuzz in Python
Sqlite in python
StepAIC in Python
N-gram in python
LINE-Bot [0] in Python