busqueda binaria.doc

1
Datos de entrada: vec: vector en el que se desea buscar el dato tam: tamaño del vector. Los subíndices válidos van desde 0 hasta tam-1 inclusive. dato: elemento que se quiere buscar. Variables centro: subíndice central del intervalo inf: límite inferior del intervalo sup: límite superior del intervalo inf = 0 sup = tam-1 Mientras inf <= sup: centro = ((sup - inf) / 2) + inf // División entera: se trunca la fracción Si vec[centro] == dato devolver verdadero y/o pos, de lo contrario: Si dato < vec[centro] entonces: sup = centro - 1 En caso contrario: inf = centro + 1 Fin (Mientras) Devolver Falso C int busquedaBinaria(int vector[], int n, int dato) { int centro,inf=0,sup=n-1; while(inf<=sup){ centro=(sup+inf)/2; if(vector[centro]==dato) return centro; else if(dato < vector [centro] ){ sup=centro-1; } else { inf=centro+1; } } return -1; }

Upload: daniel-alonso

Post on 18-Aug-2015

213 views

Category:

Documents


0 download

TRANSCRIPT

Datos de entrada:vec: vector en el que se desea buscar el datotam: tamao del vector. Los subndices vlidos van desde 0 hasta tam-1 inclusive.dato: elemento que se quiere buscar.Variablescentro: subndice central del intervaloinf: lmite inferior del intervalosup: lmite superior del intervaloinf = 0sup = tam-1Mientras inf = sup:centro = !!sup - inf" # $" % inf ## &ivisi'n entera: se trunca la fracci'n(i vec)centro* == dato devolver verdadero +#o pos, de lo contrario: (i datovec)centro* entonces:sup = centro - 1 -n caso contrario:inf = centro % 1.in !Mientras"&evolver Falso Cint busqueda/inaria!intvector)*, int n, int dato"0 int centro,inf=0,sup=n-11 2hile!inf=sup"0 centro=!sup%inf"#$1 if!vector)centro*==dato" return centro1 else if!datovector )centro* "0sup=centro-11 3 else 0 inf=centro%11 3 3 return -113