Boucle infinie dans une variante de recherche binaire (Java)

Question

Mon but est d'entrer une clé et un tableau, puis de sortir le nombre de valeurs dans ce tableau qui sont inférieures ou égales à la clé, en utilisant la recherche binaire.

Ceci est mon code:

import java.util.*; 
import java.io.*; 

public class search { 
    public static void main(String[] args) { 
     Scanner scan = new Scanner(System.in); 
     int key = scan.nextInt(); 
     int size = scan.nextInt(); 
     int [] array = new int [size]; 

     for (int i = 0;i < size ;i++) { 
      array[i] = scan.nextInt(); 
     } 
     Arrays.sort(array); 

     System.out.println(binary(key, array)); 
    } 

    public static int binary (int key, int [] array){ 
     int lo = 0; 
     int hi = array.length - 1; 

     while (lo < hi){ 
      int mid = (lo + hi)/2; 
      if (array[mid] <= key){ 
       lo = mid; 
      } 

      else { 
       hi = mid - 1; 
      } 
     } 

     return lo + 1; 
    } 
} 

Avec la clé de données = 5, array = {2,4,6,7}, le programme fonctionne très bien. Mais le moment où il y a trois valeurs qui sont inférieures ou égales à la clé, ça va haywire. Par exemple, key = 5, array = {2,4,5,6} produit une boucle infinie. J'ai trouvé la raison de cela mais je ne vois pas comment la contourner.

Fondamentalement, la valeur mid continue d'être calculée avec la même valeur. Que puis-je faire pour contourner cela? Si le code est intrinsèquement erroné, cela signifie que le the set solution for a USACO problem était erroné.

Answer 1

La solution de l'échantillon semble très bien. Le problème avec votre code est que mid = (lo + hi)/2 arrondit vers lo, ce qui est un problème puisque les cas de mise à jour sont lo = mid et hi = mid - 1. Lorsque hi == lo + 1, dans le premier cas, aucun progrès n'est fait. Vous devriez arrondir comme le fait l'exemple: mid = (lo + hi + 1)/2 (avertissement: peut déborder sur de longs tableaux, vérifier vos contraintes).

L'exemple vérifie également si la première valeur est inférieure à la clé.

Answer 2

Votre algorithme semble correct. Mais je vois qu'il y a un problème avec l'attribution de la valeur pour mid.

int mid = (hi+lo)/2 

penser à un cas où votre

hi=4 
mid = 3 

maintenant la nouvelle valeur pour la mi sera (3 + 4)/2 = 3 (division entière)

de sorte que la boucle continue courir sans casser.

Dans ce cas, vous pouvez incrémenter la valeur de mid en vérifiant cette condition.

Mais plus efficacement, il semble mieux vérifier la valeur de mid est répétée, puis briser la boucle. Enfin, vérifier si la valeur du tableau [salut] est le même que votre tableau [milieu]

espoir que cela aiderait ..

Avoir une belle journée .. :)

EDIT

Une meilleure façon de faire serait

Changer votre boucle while pour

while(mid<hi+1){ 
} 

puis vérifier l'égalité des valeurs après la boucle ..

OU simplement mis

mid = (mid+hi+1)/2 

Answer 3

Dans votre boucle, vous devez réduire vos intervalles et exclure également l'élément que vous venez de consulter. Vous faites cela quand vous allez à gauche, mais pas quand vous allez à droite.

Vous manquez également des intervalles de longueur 1, car vous utilisez des limites inférieures et supérieures inclusives. Votre condition de boucle doit être lo <= hi. Enfin, vous en renvoyez un de trop: Les résultats doivent être 0 lorsque la clé est plus petite que le premier élément et que la longueur du tableau doit être supérieure au dernier élément.

Alors:

static int binary(int key, int[] array) 
{ 
    int lo = 0; 
    int hi = array.length - 1; 

    while (lo <= hi) { 
     int mid = (lo + hi)/2; 

     if (array[mid] <= key) { 
      lo = mid + 1; 
     } else { 
      hi = mid - 1; 
     } 
    } 

    return lo; 
} 

À mon avis, il est préférable d'utiliser un Java comme le fait habituellement la limite supérieure exclusive,. (Par exemple, un tableau de longueur n comporte des éléments aux indoces 0 à n - 1, la limite supérieure n est en dehors de la plage valide.) Si rien d'autre, il est consitent avec un autre code Java. Donc:

static int binary(int key, int[] array) 
{ 
    int lo = 0; 
    int hi = array.length; 

    while (lo < hi) { 
     int mid = (lo + hi)/2; 

     if (array[mid] <= key) { 
      lo = mid + 1; 
     } else { 
      hi = mid; 
     } 
    } 

    return lo; 
}