Algoritmos de Búsqueda en C++

Búsqueda Lineal y Búsqueda Binaria

Aplicaciones en la Vida Real

Programación y Estructuras de Datos

7 de octubre de 2025
Estructuras de Datos Algoritmos de Búsqueda en C++

Índice
1. Introducción 3
1.1. Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2. ¿Por qué son importantes? . . . . . . . . . . . . . . . . . . . . . . . . . . . 3

2. Búsqueda Lineal (Sequential Search) 3

2.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.2. Caracterı́sticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
2.3. Pseudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.4. Análisis de Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.5. Ejercicio Fácil: Sistema de Verificación de Inventario . . . . . . . . . . . . 4
2.5.1. Descripción del Problema . . . . . . . . . . . . . . . . . . . . . . . 4
2.5.2. Solución . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.5.3. Código Completo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2.5.4. Análisis del Ejercicio . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.6. Ejercicio Avanzado: Sistema de Gestión Hospitalaria . . . . . . . . . . . . 6
2.6.1. Descripción del Problema . . . . . . . . . . . . . . . . . . . . . . . 6
2.6.2. Estructura de Datos . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.6.3. Funciones de Búsqueda . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.6.4. Ventajas de este Enfoque . . . . . . . . . . . . . . . . . . . . . . . . 7

3. Búsqueda Binaria (Binary Search) 8

3.1. Definición . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.2. Principio Divide y Venceras . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.3. Caracterı́sticas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.4. Pseudocódigo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
3.5. Análisis de Complejidad . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
3.6. Comparación de Complejidades . . . . . . . . . . . . . . . . . . . . . . . . 9

4. Búsqueda Binaria Iterativa 10

4.1. Problema: Catálogo de Libros por ISBN . . . . . . . . . . . . . . . . . . . 10
4.2. Implementación Completa . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.3. Visualización del Proceso . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.4. Ventajas de la Versión Iterativa . . . . . . . . . . . . . . . . . . . . . . . . 11

5. Búsqueda Binaria Recursiva 12

5.1. Problema: Sistema de Búsqueda de Estudiantes . . . . . . . . . . . . . . . 12
5.2. Implementación Recursiva . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.3. Árbol de Recursión . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
5.4. Ventajas de la Versión Recursiva . . . . . . . . . . . . . . . . . . . . . . . 13
5.5. Desventajas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

6. Comparación entre Algoritmos 14

6.1. Tabla Comparativa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.2. ¿Cuándo usar cada algoritmo? . . . . . . . . . . . . . . . . . . . . . . . . . 14
6.2.1. Usar Búsqueda Lineal cuando: . . . . . . . . . . . . . . . . . . . . . 14

Página 2
Estructuras de Datos Algoritmos de Búsqueda en C++

6.2.2. Usar Búsqueda Binaria cuando: . . . . . . . . . . . . . . . . . . . . 14

6.3. Análisis de Rendimiento Práctico . . . . . . . . . . . . . . . . . . . . . . . 14

7. Conclusiones 15
7.1. Aprendizajes Clave . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.2. Aplicaciones en el Mundo Real . . . . . . . . . . . . . . . . . . . . . . . . . 15
7.3. Recomendaciones Finales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

8. Referencias 16

Página 3
Estructuras de Datos Algoritmos de Búsqueda en C++

1. Introducción
Los algoritmos de búsqueda son fundamentales en ciencias de la computación y se
utilizan constantemente en aplicaciones del mundo real. Este documento presenta una
guı́a completa sobre los dos algoritmos de búsqueda más importantes: búsqueda lineal
y búsqueda binaria, con ejemplos prácticos implementados en C++.

1.1. Objetivos
Comprender el funcionamiento de la búsqueda lineal y binaria

Implementar ambos algoritmos en C++

Analizar la complejidad temporal de cada algoritmo

Aplicar estos algoritmos a problemas reales

Comparar el rendimiento entre ambos métodos

1.2. ¿Por qué son importantes?

La búsqueda de información es una operación que realizamos constantemente:

Buscar un contacto en el teléfono

Encontrar un producto en un inventario

Localizar un registro en una base de datos

Verificar la existencia de un elemento en una colección

2. Búsqueda Lineal (Sequential Search)

2.1. Definición
La búsqueda lineal es el algoritmo de búsqueda más simple. Consiste en recorrer se-
cuencialmente todos los elementos de un arreglo hasta encontrar el elemento buscado o
llegar al final del arreglo.

2.2. Caracterı́sticas
Caracterı́sticas Principales
Simplicidad: Fácil de implementar y entender

No requiere orden: Funciona con datos ordenados o desordenados

Complejidad: O(n) en el peor caso

Uso: Ideal para colecciones pequeñas o no ordenadas

Página 4
 Estructuras de Datos Algoritmos de Búsqueda en C++

2.3. Pseudocódigo
Algoritmo: Búsqueda Lineal
Entrada: Arreglo A, tama~no n, elemento x
Salida: ı́ndice de x o -1 si no existe

Para i desde 0 hasta n-1 hacer:

Si A[i] == x entonces
Retornar i
Fin Si
Fin Para
Retornar -1

2.4. Análisis de Complejidad

Caso Complejidad
Mejor caso (primer elemento) O(1)
Caso promedio O(n/2) = O(n)
Peor caso (último o no existe) O(n)

Cuadro 1: Complejidad temporal de búsqueda lineal

2.5. Ejercicio Fácil: Sistema de Verificación de Inventario

2.5.1. Descripción del Problema
Una tienda pequeña necesita verificar si un código de producto existe en su inventario.
Los códigos no están ordenados y la cantidad de productos es limitada.

2.5.2. Solución
Este problema es ideal para búsqueda lineal porque:

Los datos no están necesariamente ordenados

El inventario es pequeño (pocas comparaciones)

La simplicidad del código es importante

2.5.3. Código Completo

1 // BUSQUEDA LINEAL - EJERCICIO FACIL

2 // Problema : Sistema de verificacion de inventario
3

4 # include < iostream >

5 # include < string >
6 using namespace std ;

Página 5
 Estructuras de Datos Algoritmos de Búsqueda en C++

7
8 // Funcion de busqueda lineal para encontrar un codigo
9 int buscarProducto ( string codigos [] , int n ,
10 string codigoBuscado ) {
11 // Recorremos el arreglo elemento por elemento
12 for ( int i = 0; i < n ; i ++) {
13 // Si encontramos el codigo , retornamos su posicion
14 if ( codigos [ i ] == codigoBuscado ) {
15 return i ;
16 }
17 }
18 // Si llegamos aqui , el codigo no existe
19 return -1;
20 }
21
22 int main () {
23 // Inventario de codigos de productos
24 string inventario [] = { " P001 " , " P045 " , " P102 " ,
25 " P203 " , " P305 " , " P401 " };
26 int tamanio = 6;
27
28 // Codigo que el cliente quiere comprar
29 string codigoCliente = " P203 " ;
30

31 cout << " === SISTEMA DE VERIFICACION === " << endl ;
32 cout << " Buscando : " << codigoCliente << endl ;
33
34 // Realizamos la busqueda
35 int resultado = buscarProducto ( inventario , tamanio ,
36 codigoCliente ) ;
37
38 // Mostramos el resultado
39 if ( resultado != -1) {
40 cout << " Producto encontrado en posicion : "
41 << resultado << endl ;
42 } else {
43 cout << " Producto no encontrado . " << endl ;
44 }
45
46 return 0;
47 }
48

2.5.4. Análisis del Ejercicio

Entrada: Arreglo de 6 códigos de productos

Operación: Búsqueda secuencial hasta encontrar coincidencia

Salida: Índice del producto o -1 si no existe

Complejidad: O(n) donde n = 6 elementos

Página 6
 Estructuras de Datos Algoritmos de Búsqueda en C++

2.6. Ejercicio Avanzado: Sistema de Gestión Hospitalaria

2.6.1. Descripción del Problema
Un hospital necesita un sistema para buscar pacientes usando múltiples criterios:

Búsqueda por cédula (identificación única)

Búsqueda de todos los pacientes crı́ticos

Búsqueda por rango de edad

Búsqueda por diagnóstico

2.6.2. Estructura de Datos

1 // Estructura para representar un paciente

2 struct Paciente {
3 string cedula ; // Identificacion unica
4 string nombre ; // Nombre completo
5 int edad ; // Edad del paciente
6 string diagnostico ; // Diagnostico principal
7 bool critico ; // Estado critico ( true / false )
8 };
9

2.6.3. Funciones de Búsqueda

1. Búsqueda por Cédula:
1 int buscarPorCedula ( Paciente pacientes [] , int n ,
2 string cedula ) {
3 for ( int i = 0; i < n ; i ++) {
4 if ( pacientes [ i ]. cedula == cedula ) {
5 return i ;
6 }
7 }
8 return -1;
9 }
10

2. Búsqueda de Pacientes Crı́ticos:

1 vector < int > b u s c a r P a c i e n t e s C r i t i c o s ( Paciente p [] , int n ) {
2 vector < int > criticos ;
3 for ( int i = 0; i < n ; i ++) {
4 if ( p [ i ]. critico ) {
5 criticos . push_back ( i ) ;
6 }
7 }
8 return criticos ;
9 }
10

Página 7
Estructuras de Datos Algoritmos de Búsqueda en C++

2.6.4. Ventajas de este Enfoque

Flexibilidad: Permite búsquedas por múltiples criterios

Resultados múltiples: Puede retornar varios pacientes

Eficiencia aceptable: Para bases de datos pequeñas

Mantenibilidad: Código fácil de modificar y extender

Página 8
Estructuras de Datos Algoritmos de Búsqueda en C++

3. Búsqueda Binaria (Binary Search)

3.1. Definición
La búsqueda binaria es un algoritmo eficiente que funciona dividiendo repetidamente el
espacio de búsqueda a la mitad. Requisito fundamental: el arreglo debe estar ordenado.

3.2. Principio Divide y Venceras

La búsqueda binaria sigue el paradigma divide y vencerás:

1. Dividir: Comparar el elemento del medio con el buscado

2. Conquistar: Descartar la mitad donde el elemento no puede estar

3. Repetir: Aplicar el mismo proceso a la mitad restante

3.3. Caracterı́sticas
Caracterı́sticas Principales
Eficiencia: Mucho más rápida que búsqueda lineal

Requisito: El arreglo DEBE estar ordenado

Complejidad: O(log n) en el peor caso

Uso: Ideal para grandes colecciones ordenadas

3.4. Pseudocódigo
Algoritmo: Búsqueda Binaria Iterativa
Entrada: Arreglo ordenado A, tama~no n, elemento x
Salida: ı́ndice de x o -1 si no existe

izq = 0
der = n - 1
Mientras izq <= der hacer:
medio = izq + (der - izq) / 2
Si A[medio] == x entonces
Retornar medio
Sino Si x < A[medio] entonces
der = medio - 1
Sino
izq = medio + 1
Fin Si
Fin Mientras
Retornar -1

Página 9
Estructuras de Datos Algoritmos de Búsqueda en C++

3.5. Análisis de Complejidad

Caso Complejidad
Mejor caso (elemento en el medio) O(1)
Caso promedio O(log n)
Peor caso O(log n)

Cuadro 2: Complejidad temporal de búsqueda binaria

3.6. Comparación de Complejidades

Para un arreglo de n = 1,000,000 elementos:

Búsqueda Lineal: hasta 1,000,000 comparaciones

Búsqueda Binaria: hasta log2 (1, 000, 000) ≈ 20 comparaciones

La búsqueda binaria es 50,000 veces más rápida!

Página 10
 Estructuras de Datos Algoritmos de Búsqueda en C++

4. Búsqueda Binaria Iterativa

4.1. Problema: Catálogo de Libros por ISBN
Una biblioteca digital mantiene un catálogo de miles de libros ordenados por ISBN
(número único de identificación). Se necesita encontrar rápidamente un libro especı́fico.

4.2. Implementación Completa

1 // Estructura para representar un libro
2 struct Libro {
3 int isbn ;
4 string titulo ;
5 string autor ;
6 double precio ;
7 };
8
9 // Funcion de busqueda binaria iterativa
10 int b u s q u e d a B i n a r i a I t e r a t i v a ( Libro libros [] , int n ,
11 int isbnBuscado ) {
12 int izquierda = 0;
13 int derecha = n - 1;
14
15 while ( izquierda <= derecha ) {
16 // Calculamos el punto medio
17 int medio = izquierda + ( derecha - izquierda ) / 2;
18
19 // Caso 1: Encontramos el libro
20 if ( libros [ medio ]. isbn == isbnBuscado ) {
21 return medio ;
22 }
23 // Caso 2: Buscamos en la mitad izquierda
24 else if ( isbnBuscado < libros [ medio ]. isbn ) {
25 derecha = medio - 1;
26 }
27 // Caso 3: Buscamos en la mitad derecha
28 else {
29 izquierda = medio + 1;
30 }
31 }
32 return -1; // No encontrado
33 }
34

4.3. Visualización del Proceso

Para buscar ISBN 1067 en un arreglo de 10 libros:

Iteracion 1: Rango [0, 9], Medio = 4

1067 > 1067 (medio) -> Buscar en mitad derecha

Iteracion 2: Rango [5, 9], Medio = 7

Página 11
Estructuras de Datos Algoritmos de Búsqueda en C++

1067 < 1134 (medio) -> Buscar en mitad izquierda

Iteracion 3: Rango [5, 6], Medio = 5

1067 = 1067 (medio) -> ENCONTRADO!

4.4. Ventajas de la Versión Iterativa

No usa memoria adicional (sin pila de llamadas)

Ligeramente más eficiente en tiempo de ejecución

No hay riesgo de desbordamiento de pila

Más fácil de optimizar por el compilador

Página 12
 Estructuras de Datos Algoritmos de Búsqueda en C++

5. Búsqueda Binaria Recursiva

5.1. Problema: Sistema de Búsqueda de Estudiantes
Una universidad mantiene registros de estudiantes ordenados por número de matrı́cula.
El sistema debe localizar rápidamente cualquier estudiante.

5.2. Implementación Recursiva

1 // Estructura para representar un estudiante
2 struct Estudiante {
3 int matricula ;
4 string nombre ;
5 string carrera ;
6 double promedio ;
7 };
8
9 // Funcion recursiva de busqueda binaria
10 int b u s q u e d a B i n a r i a R e c u r s i v a ( Estudiante est [] ,
11 int izquierda , int derecha ,
12 int matriculaBuscada ) {
13 // CASO BASE 1: Rango invalido
14 if ( izquierda > derecha ) {
15 return -1;
16 }
17
18 // Calculamos el punto medio
19 int medio = izquierda + ( derecha - izquierda ) / 2;
20
21 // CASO BASE 2: Encontramos el estudiante
22 if ( est [ medio ]. matricula == matriculaBuscada ) {
23 return medio ;
24 }
25

26 // CASO RECURSIVO 1: Buscar en mitad izquierda

27 if ( matriculaBuscada < est [ medio ]. matricula ) {
28 return b u s q u e d a B i n a r i a R e c u r s i v a ( est , izquierda ,
29 medio - 1 ,
30 matriculaBuscada ) ;
31 }
32 // CASO RECURSIVO 2: Buscar en mitad derecha
33 else {
34 return b u s q u e d a B i n a r i a R e c u r s i v a ( est , medio + 1 ,
35 derecha ,
36 matriculaBuscada ) ;
37 }
38 }
39

5.3. Árbol de Recursión

Para buscar matrı́cula 2020089 en 12 estudiantes, el árbol de llamadas serı́a:

Página 13
Estructuras de Datos Algoritmos de Búsqueda en C++

[0, 11] medio=5

|
+-------------+-------------+
| |
2020089 > 2020023 [6, 11] medio=8
|
+-----------+-----------+
| |
2020089 < 2022034 [6, 7] medio=6
|
2020089 = 2020089
ENCONTRADO!

5.4. Ventajas de la Versión Recursiva

Código más elegante y conciso

Refleja naturalmente la idea divide y vencerás

Más fácil de entender conceptualmente

Ideal para enseñanza y aprendizaje

5.5. Desventajas
Usa memoria adicional (pila de llamadas: O(log n))

Overhead de llamadas a función

Riesgo de desbordamiento de pila con n muy grande

Página 14
Estructuras de Datos Algoritmos de Búsqueda en C++

6. Comparación entre Algoritmos

6.1. Tabla Comparativa

Caracterı́stica Lineal Binaria

Complejidad temporal O(n) O(log n)
Requiere orden No Sı́
Complejidad espacial O(1) O(1) / O(log n)
Dificultad Muy fácil Moderada
Mejor para n pequeño Sı́ No siempre
Mejor para n grande No Sı́
Datos dinámicos Sı́ Requiere reorden

Cuadro 3: Comparación de algoritmos de búsqueda

6.2. ¿Cuándo usar cada algoritmo?

6.2.1. Usar Búsqueda Lineal cuando:
Los datos no están ordenados

El tamaño del arreglo es pequeño (n ¡100)

Los datos cambian frecuentemente

La simplicidad del código es prioritaria

6.2.2. Usar Búsqueda Binaria cuando:

Los datos están ordenados o se pueden ordenar

El tamaño del arreglo es grande (n ¿1000)

Se realizan búsquedas frecuentes

El rendimiento es crı́tico

6.3. Análisis de Rendimiento Práctico

n Lineal Binaria Ganancia

10 10 4 2.5x
100 100 7 14x
1,000 1,000 10 100x
10,000 10,000 14 714x
1,000,000 1,000,000 20 50,000x

Cuadro 4: Número de comparaciones en el peor caso

Página 15
Estructuras de Datos Algoritmos de Búsqueda en C++

7. Conclusiones
7.1. Aprendizajes Clave
1. Búsqueda Lineal: Simple pero ineficiente para grandes conjuntos. Ideal cuando
los datos no están ordenados.

2. Búsqueda Binaria: Extremadamente eficiente pero requiere datos ordenados. La

diferencia entre O(n) y O(log n) es dramática.

3. Recursión vs Iteración: Ambas son válidas. La iterativa es más eficiente en me-

moria, la recursiva es más elegante.

4. Trade-offs: Ordenar tiene costo O(n log n), que debe considerarse.

7.2. Aplicaciones en el Mundo Real

Bases de datos: Índices B-tree usan búsqueda binaria

Sistemas operativos: Búsqueda de procesos y recursos

Compiladores: Tablas de sı́mbolos

Juegos: Búsqueda de colisiones

E-commerce: Búsqueda de productos

7.3. Recomendaciones Finales

Mejores Prácticas
1. Analiza el tamaño de tus datos antes de elegir el algoritmo

2. Considera si los datos estarán ordenados

3. Para datos pequeños, la búsqueda lineal puede ser suficiente

4. Para datos grandes y ordenados, búsqueda binaria es indispensable

5. Documenta claramente el requisito de orden

6. Realiza pruebas de rendimiento con datos reales

Página 16
Estructuras de Datos Algoritmos de Búsqueda en C++

8. Referencias
Cormen, T. H., et al. (2009). Introduction to Algorithms (3rd ed.). MIT Press.

Sedgewick, R., Wayne, K. (2011). Algorithms (4th ed.). Addison-Wesley.

Stroustrup, B. (2013). The C++ Programming Language (4th ed.). Addison-Wesley.

Knuth, D. E. (1998). The Art of Computer Programming, Vol 3: Sorting and Sear-
ching. Addison-Wesley.

Página 17