Recherche rapide d'un élément de tableau.

recherche dichotomie site:http://panoramic.1fr1.net

label err

dim i%

on_error_goto err
for i%=1 to 1000000000 step 100000
  caption 0,str$(i%)
 dim s$
 s$ = string$(i%," ")
 free s$
next i%

message "Pas d'erreur"
end

err:
  off_error_goto
  message "Erreur avec i%="+str$(i%)
  terminate

dim tab$(1000),line%,a$ , a% ,list$
label cherche

' on rempli le tableau avec des polices de caractères pour simplifier
dlist 1 :font_names_load 1
for a%=1 to count(1)
  tab$(a%)=item_read$(1,a%) :list$=list$+item_read$(1,a%)+"|"
next a%
edit 2
button 3:top 3,30:caption 3,"cherche":on_click 3,cherche
end

cherche:
  a$=text$(2)
  if instr(list$,a$) > 0 then message "trouvé:" + a$:else:message "inconnu dans la liste"
return

ItemIndexInString               

Cette fonction cherche une chaîne dans une autre.  La chaîne dans laquelle on cherche, est une liste de chaînes dans laquelle les sous-chaînes sont séparées par un caractère de séparation. La fonction retournera non pas la position, mais l'indice de la sous-chaine trouvée. L'appel a le format suivant:


res% = dll_call3("ItemIndexInString",adr(string$),adr(sep$),adr(item$))

string$
liste de chaînes dans laquelle il faut chercher

sep$
tcaractère de séparation

item$
chaîne de caractères à chercher dans string$

res%
indice de item$ dans string$ si trouvé, et zéro sinon

Exemple:
dim res%,sting$,item$,sep$
item$ = "Mai"
sep$ = ","
string$ = "Janvier,Février,Mars,Avril,Mai,Juin,Juillet,Août,Septembre,Octobre,Novembre,Décembre"
res% = dll_call3("ItemIndexInString",adr(string$),adr(sep$),adr(item$))
if res%=0
  message "le mois est invalide"
else
  vous avez saisi de mois numéro "+str$(res%)
end_if

' *****************************************************************************
'  RECHERCHE DICHOTOMIQUE DANS UN TABLEAU TRIE

'          DICHO.BAS

' Exemple d'utilisation
' La recherche doit se faire sur un tableau trié
' Le tableau peut contenir n'importe quel type de données : entier, réel ,string

' La dichotomie consiste à couper le tableau en 2 et comparer la valeur du milieu
' avec celle à rechercher.
' si la valeur du milieu est supérieure à celle recherchée,on recherche alors
' dans la premiere moitié sinon dans la seconde.

' Cet algorithme est très rapide : sur un très grand tableau, il est très efficasse

DIM T(1000), i
dim premier,milieu,dernier,recherche, trouve, pos
' création d'un tableau d'entiers contenant les valeurs de 1 à 1000
for i = 1 to 1000 : t(i) = i : next i
recherche = 999 : ' valeur à rechercher
' recherche = 1110
trouve = 0 : premier = 1 : dernier = 1000
while (premier <= dernier) and trouve = 0
    milieu = int((premier + dernier)/2)
    if t(milieu) =  recherche
      trouve = 1 : pos = milieu
    else
        if t(milieu) > recherche
          dernier = milieu
        else
            premier = milieu +1
        end_if
    end_if
end_while
if trouve = 0
  message "cette valeur n'appartient pas à la liste"
else
  message "cette valeur appartient à la liste " + chr$(10)+chr$(13)+ "elle est en position: " +str$(pos)
end_if

res% = dll_call3("SearchListBox",hnd%,mode%,adr(crit$))
 

dim a$, chaine$, mot$, sep$
dim y%

dll_on "kgf.dll"

file_open_read 1,"c:\perso\langues\traducteur\dictionnaires\dico_espagnol.dat"

' Lignes de titre.
file_readln 1,a$
file_readln 1,a$

while file_eof(1)<>1

      ' maison;fs;casa;fs;
      file_readln 1,a$
      if a$="FIN" then exit_while
     
      chaine$=chaine$+left$(a$,instr(a$,";")-1)+"#"
     
end_while

sep$ = "#"
mot$="maison"
y% = dll_call3("ItemIndexInString",adr(chaine$),adr(sep$),adr(mot$))
message str$(y%)

dll_off

file_close 1

dim a$, chaine$, mot$, sep$
dim y%

dll_on "kgf.dll"

chaine$ = "#"
for y%=1 to 853
  chaine$ = chaine$ + str$(y%) + "#"
next y%
chaine$ = chaine$ + "à@voix@basse;locut;en@voz@baja;locut;"
for y%=855 to 23873
  chaine$ = chaine$ + str$(y%) + "#"
next y%
chaine$ = chaine$ + "maison" + "#" + "xxx" + "#" + "yyy" + "#"

sep$ = "#"
mot$="maison"
y% = dll_call3("ItemIndexInString",adr(chaine$),adr(sep$),adr(mot$))
message str$(y%)

dll_off