Search

#include <iostream>

int *arreglo (int n){
  int *a = new int[n];
  for (int i=0; i<n; i++) a[i] = rand() % (n*2) + 1;
  return a;
}

void print(int *a, int n){
  for (int i=0; i<n; i++)
    std::cout << a[i] << " ";
  printf("\n");
}

void swap(int &a, int &b){
  int c = a;
  a = b;
  b = c;
}

void bsort (int *a, int n){
  for (int k = n - 1; k > 0; k--)
    for(int i = 0; i < k; i++)
      if (a[i] > a[i+1]) swap(a[i], a[i+1]);
}

void shuffle(int *a, int n){
  for (int k = n - 1; k > 0; k--)
    swap(a[rand() % (k + 1)], a[k]);  
}

int cont;
bool search(int x, int *a, int n){
  for (int i = 0; i < n; i++){
    cont++;
    if (a[i]==x) return true;

  }
  return false;
}

bool randomSearch(int x, int *a, int n){

  do{

    int i = rand() % n;

    cont++;

    if (a[i] == x) return true;

  } while(true);

  return false;
}

bool sequentialSearch(int x, int *a, int n){

  int i = 0;

  while (i < n && a[i] < x) {
    cont++;
    i++;
  }
  return i < n && a[i] == x;
}

bool randomorderedsearch(int x, int *a, int n){

  int l = 0;
  int r = n-1;

  while(l <= r){

    int i = rand() % (r-(l-1)) + l;

    cont++;

    if (a[i] == x) return true;

    if (x < a[i]) r = i-1;
    else if (x > a[i]) l = i+1;
  }

  return false;
}

bool bsearch(int x, int *a, int n){

  int l = 0;
  int r = n-1;

  while(l <= r){

    int i = (l + r) / 2;

    cont++;

    if (a[i] == x) return true;

    if (x < a[i]) r = i-1;
    else if (x > a[i]) l = i+1;
  }

  return false;
}

int main(){

srand((unsigned) time(nullptr));

int n = 100;
int acumulado = 0;
int positivos = 0;
int acumulado_neg = 0;
int negativos = 0;

  for (int k = 0; k < 100; k++){
int *a = arreglo(n);
   int x = rand() % (n*2)+1;
  //int x = a[rand() % n];
    bsort(a,n);

  printf("\n\n");
  print(a,n);
  printf("\nDato que vamos a buscar: %i\n", x);
  cont = 0;


  if (bsearch(x, a, n)) {

  printf("Si está: %i\n", cont);
  acumulado += cont;
  positivos++;

  } else printf("No está: %i\n", cont);
    acumulado_neg+= cont;
    negativos++;

delete [] a;
  }
  printf("Esfuerzo promedio utilizado cuando el dato sí está: %f\n", (float)acumulado/positivos);
  printf("Esfuerzo promedio utilizado cuando el dato no está: %f\n", (float)acumulado_neg/negativos);
return 0;
}