Recherche de 2 minutes Python et ses dérivés

introduction

J'ai récemment écrit un article sur les fonctions récursives. Je n'avais pas l'intention de l'utiliser, mais c'était pour étudier, mais j'avais besoin d'une recherche efficace. Il a été sauvegardé car j'aurais dû simplement améliorer la recherche publiée de 2 minutes. Comme c'est un gros problème, je publierai que la fonction améliorée peut être utile. (Bien que j'utilise en fait Javascript au lieu de Python, et qu'il ait une implémentation différente)

Trouver n

python


def binarySearchL(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = int(l + (r - l) / 2)
    middleValue = lt[middleIndex]
    if middleValue > n:
      l, r = l, middleIndex - 1
    elif middleValue < n:
      l, r = middleIndex + 1, r
    else:
      return middleIndex
  return -1

Trouvez le plus petit supérieur à n

python


def binarySearchGt(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = math.floor(l + (r - l) / 2)  #Tronquer
    middleValue = lt[middleIndex]
    if middleValue > n and r - l > 1:
      l, r = l, middleIndex
    elif middleValue <= n:
      l, r = middleIndex + 1, r
    else:
      return middleIndex
  return -1

Trouvez le plus grand moins de n

python


def binarySearchLt(lt, n):
  l, r = 0, len(lt) - 1
  while l <= r:
    middleIndex = math.ceil(l + (r - l) / 2)  #Rassembler
    middleValue = lt[middleIndex]
    if middleValue >= n:
      l, r = l, middleIndex - 1
    elif middleValue < n and r - l > 1:
      l, r = middleIndex, r
    else:
      return middleIndex
  return -1

Recommended Posts

Recherche de 2 minutes Python et ses dérivés
[Python] Recherche de priorité de profondeur et recherche de priorité de largeur
Rechercher et lire des vidéos YouTube avec Python
Rechercher et télécharger automatiquement des vidéos YouTube avec Python
Raisonnement causal et recherche causale par Python (pour les débutants)
[python] Compresser et décompresser
Astuces Python et Numpy
[Python] pip et roue
Recherche séquentielle avec Python
Exercice Python Recherche prioritaire sur 1 largeur
Itérateur et générateur Python
[Python] Recherche (itertools) ABC167C
Dichotomie avec Python
Paquets et modules Python
Intégration Vue-Cli et Python
Recherche de bisection (python2.7) mémo
[Python] Recherche de bisection ABC155D
entrée et sortie python
Python et Ruby se séparent
Exploration avec Python et Twitter API 1 - Fonction de recherche simple
Ce n'est pas facile d'écrire Python, c'est facile d'écrire numpy et scipy
Trouvez la matrice Hermite et ses valeurs uniques en Python
recherche complète de bits python
Recherche linéaire en Python
Dichotomie avec python
Rechercher sur Twitter avec Python
Recherche récursive de fichiers et de répertoires en Python et sortie
Recherche binaire en Python
Python asyncio et ContextVar
Implémenter la recherche de priorité en profondeur (DFS) et la recherche de priorité de largeur (BFS) en python
Application pour afficher et rechercher des mémos locaux (agenda) en Python
Programmation avec Python et Tkinter
[Python] BFS (recherche de priorité de largeur) ABC168D
Python: variables de classe et d'instance
Série Python 2 et série 3 (édition Anaconda)
Python et matériel - Utilisation de RS232C avec Python -
Indentation Python et format de chaîne
division des nombres réels python (/) et division des nombres entiers (//)
Installez Python et Flask (Windows 10)
À propos des objets et des classes Python
À propos des variables et des objets Python
Apache mod_auth_tkt et Python AuthTkt
Å (Ongustorome) et NFC @ Python
Apprenez à connaître les packages et les modules Python
# 2 [python3] Séparation et commentaire
Copie superficielle Python et copie profonde
Mémo tranche python et rubis
Installation de Python et grammaire de base
Recherche de priorité de largeur / recherche bidirectionnelle (édition Python)
J'ai comparé Java et Python!
Théorie de la prophétie et sa simulation (2)
Homebrew Python - Programme de recherche YouTube
[Python] DFS (recherche de priorité en profondeur) ATC001A
Recherche binaire en Python / C ++
Algorithme en Python (dichotomie)
À propos de Python, len () et randint ()
À propos de la date et du fuseau horaire Python
Recherche de bits complète avec Python