Dichotomic search function for Sorted Array

[Guimauve]

Code updated For 5.20+

Hello everyone

There is a very fast search function for sorted array only. Sorry for the French comment and code. If soneone are willing to translate go for it !!

Regards
Guimauve

Code: Select all

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; Nom du projet : Prototype de fouille Dichotomique
; Fichier : Code Expérimental
; Version : 0.0.0
; Programmation : En progression
; Programmé par : Guimauve
; Date : 25-08-2005
; Mise à jour : 25-08-2005
; Codé pour PureBasic V3.94
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; PRINCIPE DE FONCTIONNEMENT :
;
; On regarde l'element du milieu. S'il est trop petit,
; On recommence dans la partie de droite restante, sinon
; On recommence dans la partie de gauche restante.
; Ainsi, l'espace de recherche diminue de moitié a chaque
; fois.
;
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; <<<<<<<<< ! ! ! TRÈS TRÈS TRÈS IMPORTANT ! ! ! <<<<<<<<<<
;
; LE TABLEAU SUR LEQUEL LA FOUILLE EST EFFECTUÉE DOIT ÊTRE
; TRIÉ AVANT DE COMMENCER LA FOUILLE. SI NON LA FOUILLE NE
; FONCTIONNE PAS CORRECTEMENT.
;
; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<

#Nb_Element = 5
#Max_Random = 5000

Global Dim Tableau.l(#Nb_Element)


Procedure.l DichotomicSearch(ValeurRecherchee.l)
  
  Position.l = -1
  
  Debut.l = 0
  Fin.l = #Nb_Element ; La grandeur du tableau
  
  While Debut <= Fin
    
    ; On trouve le milieu de l'espace de recherche. 
    Milieu = Round((Debut + Fin) / 2,0)
    
    ; On conserve la moitie de droite ou de gauche de l'espace de
    ; recherche
    If ValeurRecherchee < Tableau(Milieu)
      Fin = Milieu - 1
      
    ElseIf ValeurRecherchee > Tableau(Milieu)
      Debut = Milieu + 1
      
      ;Si c'est égal, nous avons trouvé et on retourne la position du milieu    
    Else    
      Debut = Fin + 1
      Position = Milieu                
      
    EndIf 
    
  Wend
  
  ProcedureReturn Position
EndProcedure 

; <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
; On met en place 6 valeurs aléatoire entre 0 et 100 dans le tableau

For index = 0 To #Nb_Element
  Tableau(index) = Random(#Max_Random)
Next 

; On trie le tableau pour que les plus petites valeurs se retrouve au début
SortArray(Tableau(),0)

Debug "On affiche le tableau"
For index = 0 To #Nb_Element
  Debug Tableau(index)
Next 

Debug "On commence à Fouiller dans le tableau"

; on passe toute les valeurs de 0 à 100 pour voir si elle se trouve dans le tableau

For index = 0 To #Max_Random
  
  ;StartTime = ElapsedMilliseconds() 
  Position = DichotomicSearch(index)
  ;ElapsedTime = ElapsedMilliseconds()-StartTime
  
 ; Debug "Temps de Fouille : " + Str(ElapsedTime)
  If Position <> -1
    Debug Str(index) + " trouvé à la position : " + Str(Position)
    Debug "La valeur dans le tableau à cet index " + Str(Position) + " : " + Str(Tableau(Position))
  EndIf 
  
Next 

[HarryE]

Replace
Milieu = Round((Debut + Fin) / 2,0)
with
Milieu = (Debut + Fin+1) >> 1
and you get an impressive speed boost!

[Dare2]

Stick RandomSeed(1) in at around line 70 so that it does the same thing everytime and the speeds even out.

I wonder why?

[Guimauve]

This is the original source code from MATLAB interpreted language :

(Sorry the source are in french)

Code: Select all

function [present, position] = fouille_dichotomique(tableau, valeur)
% FOUILLE_DICHOTOMIQUE retourne true si valeur est dans tableau, false sinon.
% La fonction retourne en plus l'indice de valeur si elle est presente.
% Pour poouvoir fonctionner, le tableau doit etre ordonne en suivant
% l'indice absolu.
%
% PARAMETRES : tableau : Le tableau de donnees trie ou l'on recherche.
%              valeur  : La valeur recherchee.
%
% ATTENTION : - La fonction doit recevoir deux parametres, sinon elle leve
%               l'erreur suivante :
%               'La fonction doit recevoir deux parametres'
%             - tableau doit etre une matrice de nombre reels triee, sinon
%               la fonction leve l'erreur suivante :
%               'Le parametre tableau doit etre une matrice de nombres reels'
%             - valeur doit etre un nombre reel, sinon la fonction leve
%               l'erreur suivante :
%               'Le parametre valeur doit etre un nombre reel'
%
% APPEL :
%           present = fouille_dichotomique([1 2 3 4 5 7 9 12], 3);
%           ou
%           [present position] = fouille_dichotomique([1 2 3 4 5 7 9 12], 3);
%--------------------------------------------------------------------------

    % STRATEGIE : On regarde l'element du milieu. S'il est trop petit,
    %             on recommence dans la partie de droite restante, sinon
    %             on recommence dans la partie de gauche restante.
    %             Ainsi, l'espace de recherche diminue de moitie a chaque
    %             fois.

    % Validation des parametres recus.
    if (nargin ~= 2)
        error('La fonction doit recevoir deux parametres');
    elseif (~isnumeric(tableau) | ~isreal(tableau))
        error('Le parametre tableau doit etre une matrice de nombres reels');
    elseif (~est_un_reel(valeur))
        error('Le parametre valeur doit etre un nombre reel');
    end;
        
    % Fouille dichotomique dans le tableau.
    % Au debut, l'espace de recherche va de 1 a numel(tableau).
    debut = 1;
    fin = numel(tableau);
    present = false;
    position = 0;
    
    while (debut <= fin)
        % On trouve le milieu de l'espace de recherche. (on peut utiliser
        % FIX aussi)
        milieu = round((debut + fin) / 2)
        
        % On conserve la moitie de droite ou de gauche de l'espace de
        % recherche
        if (valeur < tableau(milieu))
            fin = milieu - 1;
            
        elseif (valeur > tableau(milieu))
            debut = milieu + 1;
            
        %Si c'est égal, nous avons trouvé et on retourne la position du milieu    
        else    
            debut = fin + 1;
            position = milieu;                
            present = true;
        end;
    end;
    
return;

MATLAB and PB are very different. I have translated the code from MatLab directly to PB. I have not take the time to optimize everything.

Also, I have used the Random just fill the array with some value. In real life situation you will recive an array of value from nowhere and I ask you to find a value as fast as you can in large sized and sorted array (1 000 000 of index). Yes you can do it with loop like this one :

Code: Select all

For Index = 0 to 1 000 000
   If ValueSearched = Array(Index)
      Index_of_searched_Value = Index
      Break
   EndIf
Next

The only time this loop it's very fast it's when the searched value are in the first index. But if the value are not in the array you will waste your your time with this loop.

With Dichotomic search you don't need to check all index to find the value you want. If you are very lucky in 5 or 8 loops and you will find the value you are looking for. I haven't counted the number of needed loops but is less than 100 loop. It's much faster than the linear search.

Anyway thanks for your help.

@Fred

A command like :

DichotomicSearchStructuredList(ListName(), Options, OffsetDuChamp, Type [, Debut, Fin])

will be great.

Regards
Guimauve

[netmaestro]

The common english term for that search technique is "Binary Search", at least where I come from (Canada). It is a very quick search, and because 2^20=1048576 it will search an array of over one million items in 20 loops or less. Being binary, two million items only costs one extra loop, which is neat.