Comment utiliser l'algorithme de recherche binaire en C++

Comment utiliser l'algorithme de recherche binaire en C++

L'algorithme de recherche binaire (Binary Search) est un algorithme de recherche efficace qui divise un ensemble de données ordonné en deux moitiés, chaque fois au milieu de l'ensemble de données Effectuer une recherche et rétrécir continuellement la plage de recherche en comparant la valeur en position médiane avec la valeur cible jusqu'à ce que la valeur cible soit trouvée ou qu'il soit déterminé que la valeur cible n'existe pas. Ce qui suit présente comment utiliser l'algorithme de recherche binaire en C++ et donne des exemples de code spécifiques.

1. Déterminer la portée de la recherche
   Avant d'utiliser l'algorithme de recherche binaire, vous devez d'abord vous assurer que l'ensemble de données à rechercher est ordonné. Par exemple, nous avons un tableau ordonné de nombres entiers dans lequel nous voulons rechercher une certaine valeur cible cible.
2. Définir la fonction de recherche binaire
   En C++, nous pouvons définir une fonction pour implémenter l'algorithme de recherche binaire. Les paramètres d'entrée de cette fonction incluent le tableau à rechercher, les positions de début et de fin du tableau et la valeur cible cible. La valeur de retour de la fonction est l'index de la valeur cible dans le tableau. Si la valeur cible n'existe pas, une valeur spécifique (telle que -1) peut être renvoyée.

La définition spécifique de la fonction est la suivante :

int binarySearch(int nums[], int start, int end, int target) {
    // 定义二分搜索的起始位置和结束位置
    int left = start;
    int right = end;
    
    while (left <= right) {
        // 计算中间位置
        int mid = left + (right - left) / 2;
        
        // 如果中间位置的值等于目标值，直接返回索引
        if (nums[mid] == target) {
            return mid;
        }
        
        // 如果中间位置的值大于目标值，更新结束位置
        else if (nums[mid] > target) {
            right = mid - 1;
        }
        
        // 如果中间位置的值小于目标值，更新起始位置
        else {
            left = mid + 1;
        }
    }
    
    // 目标值不存在，返回-1
    return -1;
}

3. Appelez la fonction de recherche binaire
   En appelant la fonction de recherche binaire, nous pouvons obtenir l'index de la valeur cible dans le tableau. Par exemple, nous avons un tableau ordonné nums et nous souhaitons rechercher la valeur cible cible. La fonction de recherche binaire peut être appelée en utilisant le code suivant :

int nums[] = {1, 3, 5, 7, 9};
int n = sizeof(nums) / sizeof(nums[0]);
int target = 5;
int index = binarySearch(nums, 0, n - 1, target);

if (index != -1) {
    cout << "目标值的索引为：" << index << endl;
}
else {
    cout << "目标值不存在！" << endl;
}

Dans le code ci-dessus, nous définissons d'abord un tableau ordonné nums, puis calculons la longueur n du tableau. Ensuite, la valeur cible cible est définie et la fonction de recherche binaire binaireSearch est appelée pour rechercher l'index de la valeur cible. Enfin, la sortie est basée sur le résultat renvoyé par la fonction.

Grâce aux étapes ci-dessus, nous pouvons utiliser l'algorithme de recherche binaire en C++ pour effectuer des opérations de recherche efficaces. Dans les applications pratiques, la fonction de recherche binaire peut être appelée selon des scénarios et des exigences spécifiques, et un traitement ultérieur peut être effectué sur la base des résultats renvoyés.

Résumé
L'algorithme de recherche binaire est un algorithme de recherche efficace adapté aux collections de données ordonnées. En C++, nous pouvons effectuer une recherche en définissant une fonction de recherche binaire et en passant le tableau à rechercher, la position de départ, la position de fin et la valeur cible. En mettant continuellement à jour la plage de recherche, l'index de la valeur cible peut éventuellement être trouvé. Nous espérons que l'introduction et les exemples de code de cet article pourront aider les lecteurs à mieux comprendre et appliquer l'algorithme de recherche binaire.

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!