[Procédure] Recherche Dichotomique

9 février 2012 · par · dans Les Procédures, Les Tableaux · 1 commentaire

La recherche dichotomique est une manière efficace et rapide de rechercher un élément dans une structure de données triée (Tableau trié).


Procédure Recherche_Dichotomique(AChercher, n: entier; T: tab[1..n]: entier);

Var	
	min, max, posInter, position: entier;

Debut
	
	min := 1;
	max := n;
	posInter := (min + max) / 2;
	
	TantQue non((max - min) =< 1) OU (AChercher = T[posInter]) Faire
		Si (AChercher < T[posInter]) Alors
			max := posInter;
		Sinon
			min := posInter;
		FinSi
		posInter := (min + max) / 2;
	FinTantQue
	
	Si (AChercher = T[posInter]) Alors
		position := posInter;
	Sinon
		position := 0;
	FinSi
	
	Si (position = 0) Alors
		Ecrire("La valeur: ", AChercher, " n'est pas dans ce tableau");
	Sinon
		Ecrire("La valeur: ", AChercher, " est au rang ", position);
	FinSi
	
Fin;
Étiquettes : , , , ,

un commentaire

  1. Aurel · · Réponse→

    impossible de faire fonctioner cette algo dans un autre if dans le while pour ma part 

    while((!(($max - $min) &lt;= 1)) || ($find == $tab[$posinter]))  
	{
		
		if ($tab[$posinter] == $find) 
		{
			$position = $posinter; 
			return ((int)$position + 1);
		}
		if ($find &lt; $tab[$posinter])
		{
			echo &quot;dans le if \n&quot;;
			$max = $posinter;
		}
		else
		{
			echo &quot;dans le else \n&quot;;
			$min = $posinter;
		}
		
		$posinter = ($min + $max) / 2;

	}

Laisser des commentaires: