Recherche binaire || Python || Structures de données et algorithmes

Recherche binaire

La

Recherche binaire est un algorithme qui divise à plusieurs reprises l'espace de recherche en deux. Cette technique de recherche suit la stratégie diviser pour mieux régner. L'espace de recherche se réduit toujours de moitié à chaque itération, ce qui entraîne une complexité temporelle de O(log(n)), où n est le nombre d'éléments.

Condition : Les tableaux doivent être triés mais ils peuvent également être appliqués à des fonctions monotones où nous devons trouver l'augmentation ou la diminution monotone.

Cela fonctionne lorsque nous devons affiner l'espace de recherche en temps logarithmique.

Nous utilisons deux pointeurs, gauche et droite. Faites la moyenne de gauche et de droite pour trouver l'élément médian.

Maintenant, nous vérifions où nous devons déplacer nos pointeurs gauche et droit en fonction de la condition.

Principalement, trois étapes sont nécessaires pour résoudre un problème :

1. Pré-traitement : Triez l'entrée si elle n'est pas triée.
2. Recherche binaire : Utilisez deux pointeurs et trouvez le milieu pour diviser l'espace de recherche, puis choisissez la bonne moitié en conséquence.
3. Post-traitement : Déterminez le résultat.

Avantages de l'algorithme de recherche binaire - La recherche binaire est plus rapide que la recherche linéaire pour les données volumineuses car elle coupe le tableau de moitié à chaque fois, au lieu de vérifier chaque élément un par un. Cela le rend plus rapide et plus efficace.

Limitations : La recherche binaire ne fonctionne que sur les tableaux triés, elle n'est donc pas efficace pour les petits tableaux non triés car le tri prend plus de temps. Cela ne fonctionne pas non plus aussi bien que la recherche linéaire pour les petites recherches en mémoire.

Applications : Il est utilisé pour rechercher un élément dans un tableau trié avec une complexité temporelle O(log(n)) et il peut également être utilisé pour trouver le plus petit ou le plus grand élément du tableau.

Code de recherche binaire de base -

Code

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

33. Rechercher dans un tableau trié avec rotation
Étant donné le tableau nums après la rotation possible et une cible entière, renvoie l'index de la cible s'il est en nombres, ou -1 s'il n'est pas en nombres.
Vous devez écrire un algorithme avec une complexité d'exécution O(log n).
Exemple 1 :
Entrée : nums = [4,5,6,7,0,1,2], cible = 0
Sortie : 4

Exemple 2 :
Entrée : nums = [4,5,6,7,0,1,2], cible = 3
Sortie : -1

Exemple 3 :
Entrée : nums = [1], cible = 0
Sortie : -1

Code

def binarySearch(nums, target):
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1

    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

1. Utilisez deux pointeurs, gauche et droite, et répétez jusqu'à ce qu'ils se chevauchent.
2. Trouvez l'élément intermédiaire.
3. Puisque le tableau est trié mais pivoté, nous ne pouvons pas simplement comparer les éléments gauche ou droit avec le milieu.
4. Tout d'abord, déterminez quelle partie gauche ou droite est triée en comparant le pointeur central avec le pointeur gauche ou droit.
5. Sur la base de cette conclusion, ajustez les pointeurs en conséquence.

Complexité temporelle - O(log(n)) car l'espace de recherche est divisé en deux à chaque itération.
Complexité spatiale - O(1)

Augmentation monotone

162. Trouver l'élément Peak

Un élément pic est un élément strictement supérieur à ses voisins.
Étant donné un tableau d'entiers indexés à 0, recherchez un élément de pointe et renvoyez son index. Si le tableau contient plusieurs pics, renvoyez l'index à l'un des pics.
Vous pouvez imaginer que nums[-1] = nums[n] = -∞. Autrement dit, un élément est toujours considéré comme strictement supérieur à un voisin extérieur au tableau.
Vous devez écrire un algorithme qui s'exécute en un temps O(log n).

Exemple 1 :
Entrée : nombres = [1,2,3,1]
Sortie : 2
Explication : 3 est un élément de pointe et votre fonction doit renvoyer le numéro d'index 2.
Exemple 2 :
Entrée : nombres = [1,2,1,3,5,6,4]
Sortie : 5
Explication : Votre fonction peut renvoyer soit le numéro d'index 1 où l'élément de pic est 2, soit le numéro d'index 5 où l'élément de pic est 6.

Code

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        left = 0
        right = len(nums)-1

        while left <= right:

            mid = (left + right)//2
            print(f'left is {left},right is {right} and mid is {mid}')
            if nums[mid]==target:
                return mid

            if nums[mid] >= nums[left]:
                # if nums[mid]< target and target >= nums[left]:
                if nums[left] <= target < nums[mid]:
                    right = mid -1
                else:
                    left = mid +1
            else:
                # if nums[mid] < target and target <= nums[right]:
                if nums[mid] < target <= nums[right]:
                    left = mid +1
                else:
                    right = mid - 1

        return -1

1. Dans ce type de problème, il faut vérifier le pic en comparant l'élément gauche ou droit du milieu.
2. Cela permet de déterminer si le graphique a une tendance à la hausse ou à la baisse.
3. Pour trouver le maximum, recherchez la pente ascendante et explorez le bon sous-espace.
4. Pour trouver le minimum, recherchez le sous-espace de gauche

Complexité temporelle - O(log(n)) car l'espace de recherche est divisé en deux à chaque itération.
Complexité spatiale - O(1)

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!