IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

avec Java Discussion :

Recherche dichotomique dans un tableau de String


Sujet :

avec Java

  1. #1
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2020
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Morbihan (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2020
    Messages : 39
    Points : 13
    Points
    13
    Par défaut Recherche dichotomique dans un tableau de String
    Bonjour à tous,

    j'aimerais savoir comment on effectue une recherche dichotomique dans un tableau de String en utilisant "s1.compareto(s2)"

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
     
    public static int rechercheDicho(String cherche , String [] t) {
                int debut = 0;
                int fin = t.length-1;
                boolean trouve = false;
     
                for(int i =0;i<t.length;i++) {
                 int resul = cherche.compareTo(t[i]);
     
                int milieu = (debut + fin)/2;
                while(debut <= fin && ! trouve ) {
                    if(t[milieu] == resul) {
                        trouve = true;
                    }else if(resul > cherche) {
                        fin = milieu-1;
                    }else {
                        debut = milieu +1;
     
                    }
                    milieu = (debut+fin)/2;
     
                    } if(trouve) {
                        return milieu;
                    }else {
                    return -1;
                    }
                }
                }
    Mais le truc c'est que concrètement, je sais pas où placer le "compareTo" car je sais qu'il renvoi une valeur, et je crois que cette valeur dépend du placement des lettres dans l'alphabets et retourne un entier mais ça j'ai pas très bien compris exactement, en gros on va comparer la valeur que nous donne compare to et on va le comparer avec le milieu du tableau?

  2. #2
    Membre expérimenté Avatar de Cincinnatus
    Homme Profil pro
    Développeur d'applications métier
    Inscrit en
    mars 2007
    Messages
    554
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Développeur d'applications métier
    Secteur : Service public

    Informations forums :
    Inscription : mars 2007
    Messages : 554
    Points : 1 516
    Points
    1 516
    Par défaut
    Citation Envoyé par antares56 Voir le message

    Mais le truc c'est que concrètement, je sais pas où placer le "compareTo" car je sais qu'il renvoi une valeur, et je crois que cette valeur dépend du placement des lettres dans l'alphabets et retourne un entier mais ça j'ai pas très bien compris exactement, en gros on va comparer la valeur que nous donne compare to et on va le comparer avec le milieu du tableau?
    Bonjour,

    Non, ça serait comparer des choux et des carottes.
    compareTo retourne un résultat de comparaison (int, > 0, 0 ou < 0) selon la valeur relative des données comparées.
    Alors comparer un int et un String, euh, ça donne quoi ?

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    if(t[milieu] == resul)
    Là par exemple, quel est le sens de cette comparaison ?
    D'ailleurs, dans ce code, à quoi sert 'resul' ?

    Enfin, le == ne doit pas être utilisé avec les Strings, il faut utiliser le equals().

  3. #3
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2020
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Morbihan (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2020
    Messages : 39
    Points : 13
    Points
    13
    Par défaut
    Merci de votre réponse !
    En faites, justement je me demande avec quoi comparer "compareTo" , il faut bien le comparer avec le milieu du tableau ?

  4. #4
    Membre expérimenté Avatar de Cincinnatus
    Homme Profil pro
    Développeur d'applications métier
    Inscrit en
    mars 2007
    Messages
    554
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Nord (Nord Pas de Calais)

    Informations professionnelles :
    Activité : Développeur d'applications métier
    Secteur : Service public

    Informations forums :
    Inscription : mars 2007
    Messages : 554
    Points : 1 516
    Points
    1 516
    Par défaut
    Citation Envoyé par antares56 Voir le message
    Merci de votre réponse !
    En faites, justement je me demande avec quoi comparer "compareTo" , il faut bien le comparer avec le milieu du tableau ?
    La recherche dichotomique joue sur la division de l'ensemble recherché (ici les Strings dans le tableau) en 2 puis encore en 2 etc pour "cerner" l'objectif et trouver rapidement la valeur recherchée.
    Ici début, fin et milieu sont donc des positions dans le tableau.
    cherche et t[x], avec x = milieu ou quelque position dans ce tableau, sont des Strings.
    compareTo est une méthode, fonction ou opération selon le point de vue, qui s'applique à un objet, dans ce code de type String, pour retourner un résultat de comparaison. Son emploi est implicite dans A > B.
    trouve est un témoin indiquant que la valeur de "cherche" existe dans au moins un élément du tableau t.

    Donc, que vient faire resul dans cette recherche ? Et pourquoi y a-t-il une boucle for englobante ? La recherche dichotomique s'effectue dans la boucle while.

  5. #5
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2020
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Morbihan (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2020
    Messages : 39
    Points : 13
    Points
    13
    Par défaut
    Citation Envoyé par Cincinnatus Voir le message
    La recherche dichotomique joue sur la division de l'ensemble recherché (ici les Strings dans le tableau) en 2 puis encore en 2 etc pour "cerner" l'objectif et trouver rapidement la valeur recherchée.
    Ici début, fin et milieu sont donc des positions dans le tableau.
    cherche et t[x], avec x = milieu ou quelque position dans ce tableau, sont des Strings.
    compareTo est une méthode, fonction ou opération selon le point de vue, qui s'applique à un objet, dans ce code de type String, pour retourner un résultat de comparaison. Son emploi est implicite dans A > B.
    trouve est un témoin indiquant que la valeur de "cherche" existe dans au moins un élément du tableau t.

    Donc, que vient faire resul dans cette recherche ? Et pourquoi y a-t-il une boucle for englobante ? La recherche dichotomique s'effectue dans la boucle while.
    J'ai fait une boucle for englobant le tout pour faire int resul = cherche.compareTo(t[i]) ,en gros je voulais avec le for comparer cherche avec t[i] avec tout les éléments du tableau , stocker cette valeur dans "resul" et comparer resul avec le milieu du tableau, finalement comme tu dis ça n'a aucun sens

  6. #6
    Membre averti
    Avatar de Rony Rauzduel
    Homme Profil pro
    En formation Architecte logiciel
    Inscrit en
    décembre 2008
    Messages
    550
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Gironde (Aquitaine)

    Informations professionnelles :
    Activité : En formation Architecte logiciel
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : décembre 2008
    Messages : 550
    Points : 404
    Points
    404
    Par défaut
    Bonjour,

    Tu n'as pas à utiliser la méthode compareTo(T o), tu utilises tout simplement la recherche dichotomique classique.
    Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
     
    for(int i =0;i<t.length;i++) {
        int resul = cherche.compareTo(t[i]);
    à supprimer du code puis ajouter au dessous de dès que la valeur est trouvée on la renvoi tout de suite.
    Tu supprimes le test en fin de code, et tu retournes -1 si et seulement si tu n'a pas trouvé la valeur dans ton tableau.

  7. #7
    Membre à l'essai
    Homme Profil pro
    Étudiant
    Inscrit en
    avril 2020
    Messages
    39
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Morbihan (Bretagne)

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : avril 2020
    Messages : 39
    Points : 13
    Points
    13
    Par défaut
    Merci j'ai enfin trouver grâce à vous tous !

+ Répondre à la discussion
Cette discussion est résolue.

Discussions similaires

  1. Réponses: 6
    Dernier message: 14/08/2014, 11h10
  2. rechercher un mot dans un tableau de string
    Par sihammaster dans le forum VB.NET
    Réponses: 8
    Dernier message: 02/04/2010, 11h45
  3. recherche dichotomique dans un tableu de String
    Par new_wave dans le forum Algorithmes et structures de données
    Réponses: 3
    Dernier message: 23/02/2007, 11h53
  4. Réponses: 23
    Dernier message: 10/01/2006, 13h33
  5. Réponses: 6
    Dernier message: 05/01/2006, 14h23

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo