Búsqueda Binaria con Duplicados

31 Jul, 2023 Programación 0

Estoy haciendo este ejercicio en particular donde tengo que implementar el algoritmo de búsqueda binaria que devuelve el índice de la primera ocurrencia de un elemento en un array ordenado, en caso de que contenga duplicados. Como estoy trabajando principalmente en mis habilidades algorítmicas en C++, solo estoy tratando de hacerlo en C++. Aquí está mi código:

#include <iostream>
#include <cassert>
#include <vector>

using std::vector;

int binary_search(const vector<int> &a, int x, int n) {
  int left = 0, right = n-1; 

  while(left<= right){
    int mid = left + (right-left)/2;
    if(x== a[mid]){
      return mid;
    }else if(a[mid]>x){
      right = mid-1;
    }else{
      left = mid+1;
    }
  }
      return -1;
}


int first_occurence(const vector<int>&a, int x, int n) {
  int out = binary_search(a, x, n);
  if(out !=-1){
     for(int i = out;i>0&& a[i]==x;--i ){
        out = i;
     }
  }
  return out;
}

int main() {
  int n;
  std::cin >> n;
  vector<int> a(n);
  for (size_t i = 0; i < a.size(); i++) {
    std::cin >> a[i];
  }
  int m;
  std::cin >> m;
  vector<int> b(m);
  for (int i = 0; i < m; ++i) {
    std::cin >> b[i];
  }
  for (int i = 0; i < m; ++i) {
    std::cout << first_occurence(a, b[i], n) << " ";
  }
}

La primera entrada al programa indica cuántos elementos debería contener el array, la segunda es la enumeración de estos elementos, la tercera línea indica cuántas claves se buscarán y la última línea son las claves individuales. La salida son los índices para la clave o -1 cuando no se encuentra dicha clave.

Mi estrategia es utilizar una función para encontrar el índice de una clave. Si se encuentra, entonces en caso de duplicados, la primera ocurrencia debe tener un índice inferior. Eso es lo que hace el método first_occurence(); sigue iterando hasta que se encuentre la primera ocurrencia.

Para la siguiente entrada:

10
1 5 4 4 7 7 7 3 2 2
5
4 7 2 0 6

La salida es:

-1 4 -1 -1 -1

Lo cual es correcto solo para la clave 7. He estado tratando de depurar esto durante bastante tiempo, pero no logro encontrar el problema.

davy.ai

July 31, 2023 at 5:36 pm

Parece haber un problema con el bucle for dentro de la función first_occurence(). Específicamente, la condición del bucle a[i] == x debe comprobarse antes de la operación de decremento --i, de lo contrario podría omitir la primera aparición de un elemento duplicado.

Para solucionar esto, modifica la condición del bucle a i > 0 && a[i-1] == x. Esto asegura que el bucle se detenga en la primera aparición de x al verificar si el elemento anterior también es igual a x.

Aquí está la función first_occurence() corregida:

int first_occurence(const vector<int>& a, int x, int n) {
    int out = binary_search(a, x, n);
    if (out != -1) {
        for (int i = out; i > 0 && a[i-1] == x; --i ) {
            out = i - 1;
        }
    }
    return out;
}

Con este cambio, la salida para la entrada dada ahora es:

2 4 8 -1 -1

lo cual es correcto para todas las claves.

Answer

davy.ai

July 31, 2023 at 5:36 pm
Parece haber un problema con el bucle for dentro de la función first_occurence(). Específicamente, la condición del bucle a[i] == x debe comprobarse antes de la operación de decremento --i, de lo contrario podría omitir la primera aparición de un elemento duplicado.

Para solucionar esto, modifica la condición del bucle a i > 0 && a[i-1] == x. Esto asegura que el bucle se detenga en la primera aparición de x al verificar si el elemento anterior también es igual a x.

Aquí está la función first_occurence() corregida:
```
int first_occurence(const vector<int>& a, int x, int n) {
    int out = binary_search(a, x, n);
    if (out != -1) {
        for (int i = out; i > 0 && a[i-1] == x; --i ) {
            out = i - 1;
        }
    }
    return out;
}
```
Con este cambio, la salida para la entrada dada ahora es:
```
2 4 8 -1 -1
```
lo cual es correcto para todas las claves.

Comments are closed.

es.davy.ai

¿Tienes una pregunta?

Búsqueda Binaria con Duplicados

Answer

davy.ai