Algorithme en Python (dichotomie)

introduction

J'étais libre à cause de l'influence du virus corona ... (Omis ci-dessous) L'arbre Seg précédent étant lourd, je résumerai cette fois la dichotomie qui peut être mise en œuvre relativement facilement.

Façon de penser

Si une limite se rencontre et ne se rencontre pas, vous pouvez rechercher cette limite avec ** O (logN) **. Par exemple, supposons que vous ayez la liste suivante, avec ** x ** pour ceux qui ne remplissent pas les conditions et ** o ** pour ceux qui remplissent.            xxxxxxoooooo

Compte tenu de l'indice 0, la dichotomie est efficace lorsque vous souhaitez trouver le 5e ou le 6e (à gauche ou à droite de la limite). Attribuez le côté gauche de la plage de recherche à la ** gauche ** et le côté droit à la variable ** droite **. Ajoutez-les et divisez par 2 (tronqué) comme ** mid ** pour déterminer si l'élément avec l'index ** mid ** remplit les conditions. Si tel est le cas, il n'y a pas de limite à sa droite, alors mettez à jour la valeur de ** right ** à ** mid ** et tronquez le côté droit. Au contraire, s'il n'est pas satisfait, il n'y a pas de limite à gauche de celui-ci, alors mettez à jour la valeur de ** left ** à ** mid **. De cette façon, la section est réduite de moitié à chaque fois, et finalement la recherche se termine lorsque ** droite ** et ** gauche ** sont côte à côte. À ce stade, ** right ** a toujours l'index de l'élément qui satisfait la condition, et ** left ** a l'index de l'élément qui ne satisfait pas, donc dans l'exemple ci-dessus, ** left ** vaut 5, ** right ** a une valeur de 6.

Exemple 1

Dans ** [2, 5, 7, 9, 10, 18, 29] **, considérez le plus petit indice égal ou supérieur à 9. Si la condition est égale ou supérieure à 9, ce sera ** xxxoooo **, qu'elle soit satisfaite ou non, donc la réponse finale est la valeur de ** right **.

code

a = [2, 5, 7, 9, 10, 18, 29]

left = 0
right = len(a) - 1

while right - left > 1:
    mid = (right + left) // 2
    if a[mid] >= 9:
        right = mid
    else:
        left = mid

print(right) # 3

Exemple 2

Puisqu'il s'agit d'un gros problème, résolvez ** Achetez un entier ** de ABC146-C à partir des questions passées d'atcoder. En ce qui concerne les candidats 1 à 10 ^ 9, il existe une limite que vous pouvez acheter du côté gauche et non du côté droit, vous devez donc chercher en deux. Cette fois, nous chercherons directement des entiers au lieu d'index. (Si vous faites une liste, c'est TLE) En guise de mise en garde, si vous ne pouvez pas en acheter un et si vous pouvez tout acheter, il n'y a pas de limite, il semble donc préférable de séparer les boîtiers.

code

import sys

a, b, x = [int(x) for x in input().split()]

left = 1
right = 10**9

if a*right + b*len(str(right)) <= x:
    print(right)
    sys.exit()

if a*left + b*len(str(left)) > x:
    print(0)
    sys.exit()

while right - left > 1:
    mid = (right + left) // 2
    if a*mid + b*len(str(mid)) <= x:
        left = mid
    else:
        right = mid

print(left)

Bissecte standard de la bibliothèque

Il peut être utilisé pour la dichotomie pour déterminer s'il est inclus dans la liste et pour trouver l'index contenant l'élément que vous souhaitez insérer. Vous pouvez le faire vous-même car il y a longtemps fait par vous-même, mais il est normal d'utiliser ** bisect ** de la bibliothèque standard. pense. (Je pense qu'il est nécessaire de s'entraîner à l'utiliser)

Recommended Posts

Algorithme en Python (dichotomie)
Dichotomie avec Python
Recherche binaire en Python
Algorithme en Python (ABC 146 C Dichotomy
Recherche binaire en Python / C ++
Algorithme en Python (recherche de priorité de largeur, bfs)
Algorithme en Python (recherche de priorité en profondeur, dfs)
Algorithme génétique en python
Recherche de bisection (python2.7) mémo
[Python] Recherche de bisection ABC155D
Algorithme en Python (méthode Bellman-Ford, Bellman-Ford)
Recherche linéaire en Python
Dichotomie avec python
Dichotomie avec Python 3
Algorithme en Python (Dijkstra)
Algorithme en Python (jugement premier)
Algorithme de recherche utilisant word2vec [python]
Reproduire la méthode de division mutuelle euclidienne en Python
Implémenter l'algorithme de Dijkstra en python
Algorithme Python
Algorithme de tri et implémentation en Python
Enregistrez le fichier binaire en Python
Ecrire des algorithmes A * (A-star) en Python
Développons un algorithme d'investissement avec Python 2
Créer un fichier binaire en Python
Écrire une recherche de priorité en profondeur en Python
[Algorithme de langage C] arbre de recherche binaire
Implémentation d'un algorithme simple en Python 2
Algorithme (arborescence de segments) en Python (s'entraîner)
Exécutez un algorithme simple en Python
Recherche de priorité de profondeur à l'aide de la pile en Python
Python en optimisation
CURL en Python
Métaprogrammation avec Python
Python 3.3 avec Anaconda
Géocodage en python
Méta-analyse en Python
Mémorandum Python (algorithme)
Unittest en Python
Livre Ali en python: méthode Dyxtra Sec.2-5
Essayez de travailler avec des données binaires en Python
Rechercher et lire des vidéos YouTube avec Python
Époque en Python
Discord en Python
Rechercher le labyrinthe avec l'algorithme python A *
Allemand en Python
DCI en Python
visualiser la recherche binaire
tri rapide en python
nCr en python
N-Gram en Python
Algorithme de recherche de chaînes
Programmation avec Python
Plink en Python
Constante en Python
ABC146C (dichotomie)
Ecrire une méthode de cupidité simple en Python