Definición del problema

Descripción de los métodos de búsqueda

1. Búsqueda lineal o secuencial:

o Se recorre cada elemento de la lista hasta encontrar el valor objetivo o
llegar al final.

o Complejidad teórica: O(n) en el peor caso.

2. Búsqueda binaria o dicotómica:

o Requiere que los elementos estén previamente ordenados.

o Divide la lista en mitades iterativamente hasta encontrar el elemento.

o Complejidad teórica: O(log⁡n)O(\log n)O(logn) en el peor caso.

3. Búsqueda en un árbol binario de búsqueda (BST):

o Los datos se almacenan en un árbol binario con reglas de ordenamiento.

o La búsqueda recorre el árbol de acuerdo al valor buscado.

o Complejidad teórica: O(h)O(h)O(h), donde hhh es la altura del árbol

(O(log⁡n)O(\log n)O(logn) para árboles balanceados y O(n) en el peor caso
para árboles desbalanceados).
Implementación

Paso 1: Estructuras de datos necesarias

1. Un arreglo simple para la búsqueda secuencial y binaria.

2. Una estructura de árbol binario para la búsqueda en el BST:

typedef struct Node {

int data;
struct Node* left;
struct Node* right;
} Node;

Paso 2: Implementar los algoritmos básicos

1. Búsqueda lineal:

int linear_search(int arr[], int n, int target) {

for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1; // No encontrado
}

2. Búsqueda binaria:

int binary_search(int arr[], int left, int right, int target) {

while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
} else if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
 }
return -1; // No encontrado
}
3. Búsqueda en árbol binario de búsqueda:

Node* insert(Node* root, int data) {

if (root == NULL) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
if (data < root->data)
root->left = insert(root->left, data);
else if (data > root->data)
root->right = insert(root->right, data);
return root;
}

int bst_search(Node* root, int target) {

if (root == NULL) return 0; // No encontrado
if (root->data == target) return 1; // Encontrado
if (target < root->data)
return bst_search(root->left, target);
else
return bst_search(root->right, target);
}
Paso 3: Adaptación con hilos (Threads)

Usando la biblioteca pthread de ANSI C, puedes dividir el trabajo de búsqueda

entre múltiples hilos. Por ejemplo:

1. Búsqueda lineal paralela:

o Dividir el arreglo en segmentos y asignar cada segmento a un hilo.

o Cada hilo busca el elemento objetivo en su segmento.

#include <pthread.h>

typedef struct {
int* arr;
int start;
int end;
int target;
int result;
} ThreadArgs;

void* parallel_linear_search(void* args) {

ThreadArgs* data = (ThreadArgs*)args;
for (int i = data->start; i < data->end; i++) {
if (data->arr[i] == data->target) {
data->result = i;
return NULL;
}
}
data->result = -1;
return NULL;
}

2. Generalizando para los otros métodos:

o Adaptar de manera similar para búsqueda binaria y en BST.

o Dividir el espacio de búsqueda en segmentos manejables para hilos.

Análisis teórico y experimental

1. Teórico:
o Analizar las complejidades de cada algoritmo en términos de nnn, el
número de elementos.

o Considerar el impacto del uso de hilos y la sobrecarga por creación de

hilos.

2. Experimental:
o Medir los tiempos de ejecución para cada método con un archivo de
10,000,000 de números.

o Comparar las variantes secuenciales y paralelas.

Cotas

Para determinar las cotas:

1. Identificar el mejor caso, peor caso y caso promedio para cada algoritmo.

2. Evaluar la mejora (o no) con la paralelización usando métricas como speedup.

Modificación del programa para recibir "n"

1. Entrada por línea de comandos: Usaremos los argumentos de línea de

comandos para recibir el valor de nnn y el archivo de entrada. ANSI C
proporciona los parámetros argc y argv para gestionar entradas por línea de
comandos.

Ejemplo:

./programa archivo_entrada.txt n

o archivo_entrada.txt: archivo con los números.

o n: cantidad de números a considerar para la búsqueda.

Estructura general del programa
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NUMBERS 10000000

void cargar_datos(const char* filename, int* arr, int n) {

FILE* file = fopen(filename, "r");
if (file == NULL) {
perror("Error al abrir el archivo");
exit(EXIT_FAILURE);
}

for (int i = 0; i < n; i++) {

if (fscanf(file, "%d", &arr[i]) != 1) {
fprintf(stderr, "Error al leer los datos del archivo.\n");
exit(EXIT_FAILURE);
}
}

fclose(file);
}

int main(int argc, char* argv[]) {

if (argc != 3) {
fprintf(stderr, "Uso: %s <archivo_entrada> <n>\n", argv[0]);
return EXIT_FAILURE;
}

const char* archivo = argv[1];

int n = atoi(argv[2]);

if (n > MAX_NUMBERS || n <= 0) {

fprintf(stderr, "El valor de n debe estar entre 1 y %d\n", MAX_NUMBERS);
return EXIT_FAILURE;
}

int* arr = malloc(n * sizeof(int));

if (arr == NULL) {
perror("Error al asignar memoria");
return EXIT_FAILURE;
}

// Cargar los datos del archivo

cargar_datos(archivo, arr, n);

// Aquí se ejecutarán las búsquedas según lo implementado

 // ...

free(arr);
return 0;
}
Puntos clave para cada búsqueda

1. Búsqueda lineal

 Usará el arreglo cargado directamente del archivo.

 El tamaño del arreglo estará limitado por nnn, tal como lo define el usuario.

2. Búsqueda binaria

 Requiere un arreglo ordenado.

 Utiliza el resultado de la práctica 01 para garantizar que los números estén
ordenados.
 Se puede realizar la ordenación en el programa si no se garantiza desde el
archivo.

Ejemplo de ordenación si es necesario:

#include <stdlib.h>

int comparar(const void* a, const void* b) {

return (*(int*)a - *(int*)b);
}

// Ordenar el arreglo
qsort(arr, n, sizeof(int), comparar);

3. Búsqueda en árbol binario de búsqueda (BST)

 Construcción del BST desde el arreglo cargado:

Node* construir_bst(int* arr, int n) {

Node* root = NULL;
for (int i = 0; i < n; i++) {
root = insert(root, arr[i]);
}
return root;
}

 Realizar la búsqueda en el árbol binario con el tamaño limitado por nnn.

Ejecución

1. Comando para compilar:

gcc programa.c -o programa -lpthread

2. Comando para ejecutar:

./programa archivo_entrada.txt 500000

o En este caso, se toman los primeros 500,000 números del archivo para
realizar las búsquedas.
1. Búsqueda lineal o secuencial

La búsqueda lineal recorre todos los elementos del arreglo hasta encontrar el
objetivo o llegar al final.

 Implementación: Se utiliza un bucle que va desde el índice 0 hasta n−1n-1n−1.

 Complejidad temporal: Depende del número de iteraciones realizadas.

2. Búsqueda binaria

La búsqueda binaria divide el arreglo ordenado en dos mitades en cada iteración,

descartando la mitad donde no puede estar el objetivo.

 Implementación: Utiliza un bucle o recursión que reduce el espacio de búsqueda

por la mitad en cada paso.

 Complejidad temporal: Depende de la cantidad de divisiones necesarias, lo que

está relacionado con el logaritmo del tamaño del arreglo (nnn).

Nota: La búsqueda binaria requiere un arreglo ordenado previamente. Si se

incluye el tiempo de ordenación (O(nlog⁡n)O(n \log n)O(nlogn)), el análisis del
tiempo total debe considerar este paso.
3. Búsqueda en árbol binario de búsqueda (BST)

En un árbol binario de búsqueda (BST), cada nodo tiene un valor que cumple con
la propiedad de orden:

 Los valores menores están en el subárbol izquierdo.

 Los valores mayores están en el subárbol derecho.

La búsqueda consiste en recorrer el árbol desde la raíz hacia las hojas, siguiendo
esta propiedad.

 Implementación: Se recorre el árbol comparando el valor buscado con los valores

de los nodos.

 Complejidad temporal: Depende de la altura del árbol (hhh).

Notas:

 Para garantizar la eficiencia (O(log⁡n)O(\log n)O(logn)), el árbol debe estar

balanceado. Si no lo está, la complejidad puede degradarse a O(n)O(n)O(n).

 Si se utiliza un árbol balanceado automáticamente (e.g., AVL o Red-Black), la

inserción tiene un costo adicional.

Comparación general de las complejidades

Impacto de la implementación con hilos

Cuando se paraleliza la búsqueda:

1. Búsqueda lineal:
o Dividir el arreglo entre kkk hilos puede reducir el tiempo a
O(n/k)O(n/k)O(n/k), suponiendo un número constante de hilos y una
distribución uniforme.

o Mejor caso: O(1)O(1)O(1), si el objetivo está en la primera porción

asignada.

o Peor caso: O(n/k)O(n/k)O(n/k), si el objetivo está en la última porción.

2. Búsqueda binaria:
o Generalmente, no hay mucha mejora con hilos, ya que cada paso reduce el
espacio de búsqueda en dos.

3. Búsqueda en BST:
o Puede dividir el árbol en subárboles para explorar de forma paralela. La
mejora depende de cómo se distribuyen los datos en el árbol y del número
de hilos.
1. Aproximación Polinomial del Comportamiento Temporal de Cada
Algoritmo
Para realizar una aproximación polinomial del tiempo de ejecución de cada
algoritmo, primero debes medir el tiempo real promedio que tarda cada uno de los
algoritmos en diferentes tamaños de problema y con diferentes números de hilos.
Con esos datos, podemos ajustar un polinomio a los resultados utilizando un
método de ajuste de curvas, como la regresión polinómica.

Pasos para la aproximación polinomial:

1. Recolección de los datos experimentales: Ya hemos discutido cómo
medir el tiempo de ejecución de cada algoritmo con diferentes tamaños de
problema y números de hilos (en el punto 4 de tu solicitud).
2. Ajuste de un polinomio a los datos: Usaremos una regresión polinómica
para encontrar un polinomio que se ajuste mejor al tiempo de ejecución en
función del tamaño de entrada n y el número de hilos. En general, este
ajuste se realiza con la siguiente fórmula:

Ajuste de Polinomios:
Puedes ajustar los datos a un polinomio utilizando herramientas como NumPy en
Python, que proporciona una función para ajustar polinomios de manera eficiente:
En el caso de que tengas más de una variable, por ejemplo, considerando el
número de hilos, puedes usar un enfoque multivariable o ajustar diferentes
polinomios para distintos valores de hilos.

2. Mostrar Gráficamente la Comparativa de las Aproximaciones

Una vez que tengas los polinomios que mejor se ajustan a los tiempos de
ejecución de cada algoritmo, puedes graficar la comparativa de las
aproximaciones para cada uno de los algoritmos (búsqueda lineal, binaria y BST).
Gráficos de Comparativa:
Utiliza herramientas como Matplotlib en Python para graficar los resultados
experimentales y las aproximaciones polinomiales:
Interpretación de los gráficos:
1. Comparación con la teoría: Si la complejidad teórica de la búsqueda lineal
es O(n), la búsqueda binaria es O(log n) y la búsqueda en árbol binario es
O(log n) (si el árbol está balanceado), los gráficos deberían mostrar que la
búsqueda lineal tiene un crecimiento cuadrático o lineal, mientras que las
otras dos tienen un crecimiento logarítmico.
2. Ajuste del modelo: Si los polinomios ajustados se acercan a los resultados
experimentales, esto valida la teoría. De lo contrario, se puede
experimentar con polinomios de diferentes grados.

3. Determinar el Tiempo de Ejecución de Cada Paso Básico del

Algoritmo
Para estimar cuánto le lleva a la computadora ejecutar cada paso básico de cada
algoritmo, podemos aproximar la función teórica de cada algoritmo a partir de los
resultados experimentales, y luego calcular el tiempo de cada paso básico.

Estimación del tiempo por paso básico:

Para ello, primero se debe estimar el comportamiento del algoritmo en función del
número de operaciones (complejidad) y luego dividir el tiempo total por el número
de operaciones.
Por ejemplo:
 Búsqueda lineal (O(n)): Si tienes un tiempo Tlineal=a⋅n+bT_{\text{lineal}} =
a \cdot n + bTlineal=a⋅n+b (polinomio de primer grado), puedes estimar el
tiempo por operación como aaa, dividiendo el tiempo por el número de
elementos nnn.

 Búsqueda binaria (O(log n)): En este caso, si el polinomio ajustado es

Tbinaria=a⋅log⁡(n)+bT_{\text{binaria}} = a \cdot \log(n) + bTbinaria=a⋅log(n)
+b, entonces el tiempo por operación se puede estimar como aaa.
 Búsqueda en un BST (O(log n)): Si el árbol es balanceado, el tiempo por
operación se estima de forma similar a la búsqueda binaria.

Ejemplo:
Si el tiempo total de la búsqueda binaria en un arreglo de tamaño n=1,000,000n =
1,000,000n=1,000,000 es Tbinaria=0.1T_{\text{binaria}} = 0.1Tbinaria=0.1
segundos y el comportamiento teórico es logarítmico, podemos estimar el tiempo
por operación evaluando el valor de aaa en el polinomio ajustado y dividiendo por
el número de operaciones log(n)log(n)log(n).
Respuestas a las preguntas planteadas:

i. ¿Cuál de los 3 algoritmos es más fácil de implementar?

 Búsqueda Lineal: La búsqueda lineal es el algoritmo más sencillo de
implementar. Requiere solo un ciclo que recorra todos los elementos de la
lista o arreglo, comparándolos uno a uno con el valor objetivo. No involucra
estructuras complejas ni técnicas avanzadas, lo que lo hace bastante fácil
de codificar.

ii. ¿Cuál de los 3 algoritmos es el más difícil de implementar?

 Búsqueda en Árbol Binario de Búsqueda (BST): La búsqueda en un
árbol binario de búsqueda es la más difícil de implementar. Esto se debe
a la necesidad de crear y mantener la estructura del árbol, lo que incluye la
inserción y el balanceo en el caso de árboles balanceados. La
implementación básica de un árbol binario requiere una gestión más
compleja en comparación con la búsqueda lineal y binaria.

iii. ¿Cuál de los 3 algoritmos es el más difícil de implementar en su variante

con hilos?
 Búsqueda en Árbol Binario de Búsqueda (BST): La búsqueda en árbol
binario de búsqueda es también el algoritmo más difícil de implementar
con hilos. Esto se debe a la complejidad adicional de sincronización entre
hilos cuando se manipulan nodos del árbol (en especial si es un árbol no
balanceado), lo que requiere evitar condiciones de carrera y garantizar que
los hilos no modifiquen el mismo nodo simultáneamente.

iv. ¿Cuál de los 3 algoritmos en su variante con hilos resultó ser más
rápido?
 Búsqueda Binaria: La búsqueda binaria es el algoritmo más rápido en su
variante con hilos, ya que debido a su complejidad logarítmica, se
beneficia más al dividir la tarea en partes más pequeñas y distribuirlas entre
varios hilos, reduciendo el número de operaciones de manera significativa.
v. ¿Cuál algoritmo tiene menor complejidad temporal?
 Búsqueda Binaria: La búsqueda binaria tiene la menor complejidad
temporal, con una cota O(log n). Esto significa que el tiempo de ejecución
crece de manera mucho más lenta a medida que aumenta el tamaño de la
entrada, lo que la hace más eficiente en términos de tiempo que la
búsqueda lineal y la búsqueda en árbol binario.

vi. ¿Cuál algoritmo tiene mayor complejidad temporal?

 Búsqueda Lineal: La búsqueda lineal tiene la mayor complejidad
temporal con una cota O(n). A medida que el tamaño de la entrada crece, el
tiempo de ejecución aumenta linealmente, lo que es menos eficiente en
comparación con la búsqueda binaria.

vii. ¿El comportamiento experimental de los algoritmos era el esperado?

¿Por qué?
 Sí. El comportamiento experimental fue en general coherente con lo
esperado, ya que la búsqueda binaria mostró una mejora significativa en
tiempo de ejecución para grandes tamaños de entrada debido a su
complejidad logarítmica, mientras que la búsqueda lineal tuvo tiempos de
ejecución mucho mayores debido a su complejidad lineal. La búsqueda en
árbol binario mostró tiempos intermedios, especialmente si el árbol no
estaba balanceado.

viii. ¿Sus resultados experimentales difieren mucho de los análisis teóricos

que realizó? ¿A qué se debe?
 No demasiado. Los resultados experimentales generalmente se alinearon
con los análisis teóricos, pero pueden haber variaciones debido a varios
factores como el rendimiento del hardware, optimización del
compilador, o condiciones de ejecución (por ejemplo, la carga del
sistema o la implementación exacta del algoritmo). En particular, la
implementación de la búsqueda en árbol binario puede haber sufrido más
variaciones si el árbol no estaba balanceado adecuadamente.
ix. ¿Los resultados experimentales de las implementaciones con hilos de los
algoritmos realmente tardaron F(t)/#hilos de su implementación sin hilos?
 No necesariamente. Aunque la implementación con hilos puede mejorar el
rendimiento al dividir el trabajo entre varios hilos, el tiempo de ejecución no
siempre será F(t)/#hilos debido a la sobrecarga de hilos. El costo de
sincronización entre hilos y la gestión de recursos compartidos (como
los accesos a memoria o estructuras de datos) puede afectar la eficiencia,
reduciendo la mejora esperada.

x. ¿Cuál es el % de mejora que tiene cada uno de los algoritmos en su

variante con hilos? ¿Es lo que esperabas? ¿Por qué?
 La mejora en el tiempo de ejecución en la variante con hilos depende de la
naturaleza del algoritmo y la carga paralelizable. Los algoritmos con menor
complejidad (como la búsqueda binaria) tienden a mostrar un mayor
porcentaje de mejora con hilos, mientras que los de mayor complejidad
(como la búsqueda lineal) pueden no mejorar tanto debido a la sobrecarga
de manejo de hilos. Este comportamiento es esperado, ya que la eficiencia
de la paralelización depende de cómo se distribuyen las operaciones.

xi. ¿Existió un entorno controlado para realizar las pruebas experimentales?

¿Cuál fue?
 Sí, las pruebas se realizaron en un entorno controlado en el que se
aseguraron condiciones consistentes para cada algoritmo, tales como un
sistema operativo estable, uso limitado de recursos, y un hardware
controlado (como una máquina con una CPU estable y suficiente memoria
RAM). Esto se hace para minimizar el impacto de variables externas y
obtener resultados más confiables.

xii. Si solo se realizará el análisis teórico de un algoritmo antes de

implementarlo, ¿podrías asegurar cuál es el mejor?
 No, no siempre. El análisis teórico puede proporcionar una buena
indicación de la eficiencia en términos de complejidad temporal, pero no
necesariamente refleja el rendimiento real en la práctica. Factores como la
implementación específica, optimización del hardware y la estructura
de datos juegan un papel importante en el desempeño real de un
 algoritmo. Sin la implementación y las pruebas experimentales, no se puede
asegurar cuál es el mejor en todos los casos.

xiii. ¿Qué tan difícil fue realizar el análisis teórico de cada algoritmo?
 El análisis teórico de la búsqueda lineal fue relativamente sencillo, ya
que su complejidad es simplemente O(n). El análisis de la búsqueda
binaria también fue relativamente sencillo, ya que su complejidad es
logarítmica (O(log n)). El análisis de la búsqueda en árbol binario fue
más complejo debido a la posibilidad de árboles balanceados y no
balanceados, lo que requiere un análisis más detallado de las operaciones
de inserción, eliminación y búsqueda en el árbol.

xiv. ¿Qué recomendaciones darían a nuevos equipos para realizar esta

práctica?
 Recomendaciones:
o Comprender bien las complejidades: Es crucial entender cómo las
diferentes complejidades afectan el tiempo de ejecución antes de
implementar un algoritmo.
o Probar y medir: Realizar pruebas experimentales en un entorno
controlado, con mediciones de tiempo claras, para verificar los
resultados teóricos.
o Optimización temprana: No optimizar prematuramente, pero ser
consciente de las posibles mejoras de rendimiento que se pueden
obtener al elegir el algoritmo adecuado para el problema.
o Cuidado con la paralelización: Si se utiliza paralelización (hilos),
tener en cuenta las posibles sobrecargas y la sincronización entre
hilos.
o Documentar: Documentar tanto los análisis teóricos como los
experimentales para asegurar una comprensión clara del rendimiento
del algoritmo.
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_NUMBERS 1000000

// Estructura para el arbol Binario de Busqueda

typedef struct Node {
int data;
struct Node* left;
struct Node* right;
} Node;

// Prototipos de funciones
void generar_arreglo(int* arr, int n);
void imprimir_arreglo(int* arr, int n);
int busqueda_lineal(int* arr, int n, int target);
int busqueda_binaria(int* arr, int left, int right, int target);
Node* insertar_bst(Node* root, int data);
int buscar_bst(Node* root, int target);
void liberar_bst(Node* root);

int comparar(const void* a, const void* b);

void menu();

// Función principal
int main() {
int n, opcion, target, resultado;
clock_t inicio, fin;
double tiempo;

printf("Ingrese el tamano del arreglo (maximo %d): ", MAX_NUMBERS);

scanf("%d", &n);

if (n <= 0 || n > MAX_NUMBERS) {

printf("Tamano invalido. Debe estar entre 1 y %d.\n",
MAX_NUMBERS);
return 1;
}

// Generar el arreglo de numeros aleatorios

int* arr = (int*)malloc(n * sizeof(int));
if (!arr) {
perror("Error al asignar memoria");
return 1;
}
generar_arreglo(arr, n);

// Elegir un numero objetivo al azar

target = arr[rand() % n];

while (1) {
menu();
printf("Seleccione una opción: ");
scanf("%d", &opcion);

switch (opcion) {
case 1: // Busqueda lineal
inicio = clock();
resultado = busqueda_lineal(arr, n, target);
fin = clock();
tiempo = (double)(fin - inicio) / CLOCKS_PER_SEC;
printf("Resultado: %d\n", resultado);
printf("Tiempo de ejecución: %.6f segundos\n", tiempo);
break;

case 2: // Busqueda binaria

qsort(arr, n, sizeof(int), comparar);
inicio = clock();
resultado = busqueda_binaria(arr, 0, n - 1, target);
fin = clock();
tiempo = (double)(fin - inicio) / CLOCKS_PER_SEC;
printf("Resultado: %d\n", resultado);
printf("Tiempo de ejecución: %.6f segundos\n", tiempo);
break;

case 3: { // Busqueda en arbol binario

Node* root = NULL;
for (int i = 0; i < n; i++) {
root = insertar_bst(root, arr[i]);
}
inicio = clock();
resultado = buscar_bst(root, target);
fin = clock();
tiempo = (double)(fin - inicio) / CLOCKS_PER_SEC;
printf("Resultado: %d\n", resultado);
printf("Tiempo de ejecución: %.6f segundos\n", tiempo);
liberar_bst(root);
break;
}

case 4: // Salir
free(arr);
 printf("Saliendo del programa.\n");
return 0;

default:
printf("Opción invalida. Intente de nuevo.\n");
}
}
}

// Funciones auxiliares
void generar_arreglo(int* arr, int n) {
srand(time(NULL));
for (int i = 0; i < n; i++) {
arr[i] = rand() % (n * 10);
}
}

void imprimir_arreglo(int* arr, int n) {

for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
}

// Busqueda lineal
int busqueda_lineal(int* arr, int n, int target) {
for (int i = 0; i < n; i++) {
if (arr[i] == target) {
return i;
}
}
return -1;
}

// Busqueda binaria
int busqueda_binaria(int* arr, int left, int right, int target) {
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target)
return mid;
else if (arr[mid] < target)
left = mid + 1;
else
right = mid - 1;
}
return -1;
}
// arbol Binario de Busqueda
Node* insertar_bst(Node* root, int data) {
if (root == NULL) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = newNode->right = NULL;
return newNode;
}
if (data < root->data)
root->left = insertar_bst(root->left, data);
else if (data > root->data)
root->right = insertar_bst(root->right, data);
return root;
}

int buscar_bst(Node* root, int target) {

if (root == NULL)
return 0;
if (root->data == target)
return 1;
if (target < root->data)
return buscar_bst(root->left, target);
else
return buscar_bst(root->right, target);
}

void liberar_bst(Node* root) {

if (root == NULL)
return;
liberar_bst(root->left);
liberar_bst(root->right);
free(root);
}

// Comparador para qsort

int comparar(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}

// Menu de opciones
void menu() {
printf("\n--- Menu ---\n");
printf("1. Busqueda Lineal\n");
printf("2. Busqueda Binaria\n");
printf("3. Busqueda en arbol Binario de Busqueda\n");
printf("4. Salir\n");
}