Recherche binaire en 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

Recherche binaire en Python / C ++
Dichotomie avec Python
Recherche binaire en Python
Algorithme en Python (ABC 146 C Dichotomy
Algorithme en Python (dichotomie)
Ecrire une dichotomie en Python
Recherche de bisection (python2.7) mémo
[Python] Recherche de bisection ABC155D
Recherche linéaire en Python
Dichotomie avec python
Dichotomie avec Python 3
API C en Python 3
Étendre python en C ++ (Boost.NumPy)
Recherche binaire ALDS1_4_B langage C
Algorithme en Python (recherche de priorité de largeur, bfs)
Enregistrez le fichier binaire en Python
ABC166 en Python A ~ C problème
Créer un fichier binaire en Python
Algorithme en Python (recherche de priorité en profondeur, dfs)
Résoudre ABC036 A ~ C avec Python
Écrire une recherche de priorité en profondeur en Python
Comment envelopper C en Python
[Algorithme de langage C] arbre de recherche binaire
Résoudre ABC037 A ~ C avec Python
Ecrire un test unitaire de langage C en Python
Recherche de priorité de profondeur à l'aide de la pile en Python
Quadtree en Python --2
Python en optimisation
CURL en Python
Métaprogrammation avec Python
Résoudre ABC175 A, B, C avec Python
Python 3.3 avec Anaconda
Géocodage en python
SendKeys en Python
Méta-analyse en Python
Unittest en Python
Essayez de travailler avec des données binaires en Python
Implémenter le filtre FIR en langage Python et C
Rechercher et lire des vidéos YouTube avec Python
Époque en Python
Allemand en Python
DCI en Python
visualiser la recherche binaire
tri rapide en python
nCr en python
Ecrire le fichier O_SYNC en C et Python
N-Gram en Python
Programmation avec Python
notes de python C ++
Plink en Python
Constante en Python
ABC146C (dichotomie)
python, openFrameworks (c ++)
FizzBuzz en Python
Sqlite en Python
Étape AIC en Python
LINE-Bot [0] en Python