Cerca Dicotòmica

[How-to del blog antic.]

Algorisme de cerca en un vector. Una cerca dicotòmica necessita l’entrada ordenada. A grans trets, el que fa és dividir en dos el vector i seguir buscant en el tros de vector on pot estar el nostre valor.

#include <iostream>
#include <vector>
#include "stdlib.h"
using namespace std;
static void mostra_taula ( vector<int>& t ) {
	int i = 0;
	while( i < t.size() ){
		cout << t[i] << " " ;
		i++;
	}
	cout << endl;
}
static void fusiona( vector<int>& t, int inici, int mig, int fi) {
    vector<int> aux(fi - inici + 1);
    int i = inici; // index part esquerra del vector
    int j = mig + 1; // index part dreta del vector
    int k = 0; // index del vector aux
    //mentre no acabi cap index de t, l'element més petit es copia al vector aux
    while ( i <= mig and j <= fi ) {
        if ( t[i] < t[j] ) {
            aux[k] = t[i];
            ++i;
        }
        else {
            aux[k] = t[j];
            ++j;
        }
        ++k;
    }
 	//cas en què un vector ja s'ha copiat al complert
    while (i <= mig) {
        aux[k] = t[i];
        ++i;
        ++k;
    }
    while (j <= fi) {
        aux[k] = t[j];
        ++j;
        ++k;
    }
    // copia els elements guardats a aux a t
    for (int n = 0; n < aux.size(); ++n){
       	t[inici + n] = aux[n];
    }
}
static void merge_sort( vector<int>& t, int inici, int fi) {
    if ( inici < fi ) {
        int mig = ( inici + fi ) / 2;
        merge_sort( t, inici, mig);
        merge_sort( t, mig + 1, fi);
        fusiona( t, inici, mig, fi);
    }
}
static int cerca_dicotomica( vector<int> t, int x, int l, int tamany ){
	int m = (l + tamany)/2;
	if( l== tamany-1 )
		return l;
	if( x < t[m] )
		return cerca_dicotomica( t, x, l, m );
	else
		return cerca_dicotomica( t, x, m, tamany);
}
int main () {
  	//MODIFICA LA VARIABLE TAMANY PER DONAR MIDA A LA TAULA.
	int tamany = 8;
	//MODIFICA ELS DOS NOMBRES DONATS
	int x = 2;
	int y = 3;
	//ES GUARDA EL RESULTAT A LA VARIABLE
	int resultat;
	int resultatX, resultatY;
	//VECTOR AMB EL QUE ES TREBALLA
	vector<int> taula( tamany );
	int i = 0, aux;
	for (int i=0; i<taula.size(); ++i) {
  		aux = rand( ) % tamany;
  		taula[i] = aux;
	}
	//mostra_taula( taula );
	merge_sort( taula, 0, tamany);
	mostra_taula( taula );
	resultatX = cerca_dicotomica( taula, x, 0, tamany );
	resultatY = cerca_dicotomica( taula, y, 0, tamany );
	cout <<" NOMBRE DE CELES ENTRE "<< x << " i "<< y <<" = "<< resultatY - resultatX + 1 << endl;
}

Tags: C++, CPP, Programació

Articles relacionats

OOCSS (2a part), profunditzant en els widgets

OOCSS, Object-Oriented CSS

Web service amb PHP i NuSOAP

Less Framework 2

FireQuery, una extenció de Firebug per desenvolupar en jQuery