es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • Posición de inserción de búsqueda de leet-code: ¿Por qué mi búsqueda binaria no puede devolver la respuesta correcta?

Posición de inserción de búsqueda de leet-code: ¿Por qué mi búsqueda binaria no puede devolver la respuesta correcta?

05 Aug, 2023 Programación

clase Solución:

def búsqueda_binaria_recursiva(self, nums: list[int], objetivo: int, base: int):
if (len(nums) == 1):
return base

posición = int((len(nums) - 1)/2)

if (nums[posición] == objetivo):
    return base + posición + 1
elif (nums[posición] > objetivo):
    base = base + int((len(nums) - 1) / 2)
    return Solución.búsqueda_binaria_recursiva(self, nums[posición+1:], objetivo, base)
elif (nums[posición] < objetivo):
    return Solución.búsqueda_binaria_recursiva(self, nums[:posición+1], objetivo, base)

def buscarInsertar(self, nums: list[int], objetivo: int) -> int:
return Solución.búsqueda_binaria_recursiva(self, nums, objetivo, 0)

La pregunta requiere:

Dada una matriz ordenada de enteros distintos y un valor objetivo, devuelve el índice si se encuentra el objetivo. Si no, devuelve el índice donde se insertaría en orden.

Debe escribir un algoritmo con una complejidad de tiempo de ejecución O(log n).

Tags:  ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Algoritmo de búsqueda binaria en Python con una complejidad de tiempo de ejecución de O(log n)

    Este script de Python implementa un algoritmo de búsqueda binaria para buscar en un arreglo ordenado de enteros distintos y devolver el índice del valor objetivo si se encuentra o el índice donde se insertaría en orden. El algoritmo tiene una complejidad de tiempo de ejecución de O(log n).

    El método recursive_binary_search realiza la búsqueda binaria de forma recursiva dividiendo la lista en dos mitades hasta que se encuentre el valor objetivo o el tamaño de la lista se reduzca a uno. Devuelve el índice del valor objetivo, si se encuentra, o la posición donde debería estar, calculada en función de la ruta de búsqueda seguida.

    El método searchInsert llama al método recursive_binary_search con el valor base inicial establecido en 0. Devuelve el resultado de la búsqueda binaria.

    class Solution:

    def recursive_binary_search(self, nums: list[int], target: int, base: int):
        if (len(nums) == 1):
            return base

        position = int((len(nums) - 1)/2)

        if (nums[position] == target):
            return base + position
        elif (nums[position] > target):
            return Solution.recursive_binary_search(self, nums[:position], target, base)
        elif (nums[position] < target):
            base = base + position + 1
            return Solution.recursive_binary_search(self, nums[position+1:], target, base)

    def searchInsert(self, nums: list[int], target: int) -> int:
        return Solution.recursive_binary_search(self, nums, target, 0)

    Para probar el algoritmo, puedes crear un objeto Solution y llamar al método searchInsert con una lista ordenada de enteros y un valor objetivo. Por ejemplo:

    solution = Solution()
nums = [1, 3, 5, 6]
target = 5
print(solution.searchInsert(nums, target)) # Salida: 2

    En este ejemplo, la lista de entrada [1, 3, 5, 6] es un arreglo ordenado de enteros distintos, y el valor objetivo es 5. El algoritmo devuelve 2, que es el índice del valor objetivo en la lista.

Comments are closed.