Un problème dans de nombreuses implémentations de recherche binaire ?

Nous savons que l'algorithme de recherche binaire est meilleur que l'algorithme de recherche linéaire. Le temps nécessaire pour exécuter cet algorithme est O(log n). Cependant, la plupart du temps, il y a des problèmes avec le code implémenté. Considérons une fonction d'algorithme de recherche binaire comme indiqué ci-dessous -

Exemple

int binarySearch(int array[], int start, int end, int key){
   if(start <= end){
      int mid = (start + end) /2); //mid location of the list
      if(array[mid] == key)
         return mid;
      if(array[mid] > key)
         return binarySearch(array, start, mid-1, key);
         return binarySearch(array, mid+1, end, key);
   }
   return -1;
}

Cet algorithme fonctionne bien jusqu'à ce qu'il atteigne un grand nombre au début et à la fin. Si (début + fin) dépasse la valeur 2³² - 1, alors un nombre négatif peut être renvoyé après le bouclage. Étant donné que les nombres négatifs ne sont pas pris en charge comme indices de tableau, cela peut poser certains problèmes.

Pour résoudre ce problème, il existe plusieurs manières différentes.

Méthode 1

int mid = start + ((end - start) / 2)

La deuxième méthode ne fonctionne qu'en Java car il n'y a pas d'opérateur >>>

Méthode 2 (uniquement pour Java)

int mid = (start + end) >>> 1

Puisque >>> n'est pas pris en charge en C ou C++, nous pouvons utiliser la méthode suivante.

Méthode 3

int mid = ((unsigned int) low + (unsigned int) high) >> 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!