Discussion :

[djibril]

Salut,
petite question bête sur la dichotomie.
Le principe est de toujours coupé en deux afin d'arriver à ses fins.
Mais n'ayant plus de cervelle ce soir, si j'ai un tableau contenant 100 nom d'employés et que je recherche un employé en particulier, comment procéder par dichotomie pour le trouver le plus rapidement possible?
car généralement on utilise cet algo sur des tableaux d'entiers triés, et on fait des comparaisons, mais si ce sont des chaines de caractères, on fait comment?

Merci

[Jedai]

Ben exactement pareil... Sauf que la procédure de comparaison est un peu plus couteuse (cmp au lieu de <=>).

--
Jedaï

[djibril]

j'essaye de faire une procédure de recherche dans un tableau d'entiers déjà.
j'arrive plus à penser
Sauf si tu en as une sous la main, histoire de voir le code. ensuite, j'aimerais bien l'adapter à tout type de tableau, car y a pas de fonction perl pour tester l'existence d'une valeur dans un tableau. Y a surement un module pour (si tu le trouve, je veux bien), mais bon par curiosité, j'ai envie de me prendre le chou

[Jedai]

Tu parles bien d'une recherche dans un tableau trié ?
Pour généraliser il faut autoriser le programmeur à te fournir la fonction de comparaison utilisée pour trier le tableau en premier lieu.

En fait :

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
29
30
#!/usr/bin/perl
use strict; use warnings;
 
sub search {
  my ($compare, $elem, $arr) = @_;
  my ($start, $end) = (0, $#{$arr});
  while( $start <= $end ) {
    my $middle = int(($start + $end) / 2);
    my $cmp_result = do {
      local($a,$b) = ($elem,$arr->[$middle]);
      $compare->()
    };
    if( $cmp_result == 0 ) {
      return $middle;
    }
    elsif( $cmp_result < 0 ) {
      $end = $middle - 1;
    }
    else {
      $start = $middle + 1;
    }
  }
  return;
}
 
my @a = (1..20);
 
print search(sub {$a <=> $b}, 20, \@a), "\n";
 
__END__

--
Jedaï

[djibril]

pour l'instant je prends juste le tableau, à moi de le trier apres.
Ok je vais regarder ton code

[djibril]

je ne savais pas que
print $a <=> $b; renvoyer 0, 1 ou -1

Pas mal