Añadir o mover un elemento en una lista ya ordenada.

Answer

1. 

   davy.ai

   August 6, 2023 at 1:41 am

   Para agregar un elemento en una lista ordenada o mover un elemento existente, podemos usar la búsqueda binaria para encontrar la posición del elemento según el orden establecido. Una vez que tenemos el índice del elemento, simplemente lo eliminamos de su posición actual e lo insertamos en la nueva posición.

   En el ejemplo dado, podemos seguir los siguientes pasos para mover la casa vendida con el ID 789 a su nueva posición:

   val list: MutableList<house> = // lista ordenada de casas
   val soldHouse = list.binarySearch { house ->
       if (house.sold) {
           house.creationDate.compareTo(LocalDate.now()) // o cualquier otra fecha para comparar
       } else {
           1 // aseguramos que las casas vendidas vengan después de las no vendidas
       }
   }.let { index ->
       if (index >= 0) list.removeAt(index) else null // eliminamos la casa si se encuentra
   }
   if (soldHouse != null) {
       val newIndex = list.binarySearch { house ->
           if (house.creationDate.isBefore(soldHouse.creationDate)) {
               -1 // aseguramos que las casas vendidas vengan antes de las más nuevas
           } else {
               1
           }
       }.let { index ->
           if (index >= 0) index else (-index - 1) // obtenemos el índice correcto de inserción si no se encuentra
       }
       list.add(newIndex, soldHouse)
   }
   

   Aquí, primero usamos binarySearch para encontrar el índice de la casa vendida en la lista, según su fecha de creación. Si se encuentra la casa, la eliminamos de la lista y la almacenamos en una variable. Si no se encuentra la casa, devolvemos null.

   A continuación, usamos nuevamente binarySearch para encontrar el índice donde debería insertarse la casa vendida, según los mismos criterios. Si se encuentra el índice, simplemente insertamos la casa en esa posición. Si no se encuentra el índice, obtenemos el índice correcto de inserción usando la fórmula (-index - 1) e insertamos la casa en esa posición.

   Al usar la búsqueda binaria para encontrar las posiciones correctas, podemos evitar reordenar toda la lista y lograr un mejor rendimiento.

Comments are closed.