Encontrar un número en monótonamente creciente y luego decreciente sequencecera

Question

Encontrar el valor máximo o mínimo en una secuencia que aumenta monótonamente y luego disminuye monótonamente se puede hacer en O (log n).

Sin embargo, si deseo verificar si existe un número en dicha secuencia, ¿esto también se puede hacer en O (log n)?

No creo que eso sea posible. Considere este ejemplo: 1 4 5 6 7 10 8 3 2 0.

En este ejemplo, si necesito encontrar si la secuencia contiene '2', no tengo condiciones para dividir el espacio de búsqueda en la mitad el espacio de búsqueda original. En el peor de los casos, será O (n), ya que es necesario buscar las dos mitades, cuando estamos tratando de buscar 2.

Me gustaría saber si esta búsqueda se realiza en O (log n) tiempo?

Answer 1

Como ha indicado, puede encontrar el máximo (y su posición) en O (logn). Luego puedes hacer una búsqueda binaria en cada parte que también sea O (logn).

En el ejemplo anterior, se encuentra el máximo 10 en la posición 5. Luego realiza una búsqueda binaria en la subsecuencia [0..5] (1, 4, 5, 6, 7, 10). Como no se encuentra 2, se procede a hacer una búsqueda binaria en la otra parte (10, 8, 3, 2, 0).

Para encontrar el máximo en O (logn): observe los dos elementos en el centro: 7 < 10. Así que todavía estamos en la parte creciente y tenemos que buscar el máximo en la mitad derecha de la secuencia: (10, 8, 3, 2, 0). Mire 8 y 3 y proceda con la parte izquierda (10, 8).

Answer 2

Como recuerdo, la mejor búsqueda para las matrices cuyos elementos se ordenan aumentar y luego disminuir es el algoritmo de búsqueda de Fibonacci.

Answer 3

Aquí hay un boceto en python. En resumen, buscamos encontrar un elemento que limite con las regiones en aumento y disminución (esto verificamos que las dos condiciones verifiquemos los elementos vecinos). Y seguimos saltando como en la búsqueda binaria estándar hasta que encontremos este elemento. Espero que ayude.

def get_max(arr): 
    if len(arr) == 1: 
     return arr[0] 
    if len(arr) in [0,2]: 
     return None 
    left, right = 0, len(arr) - 1 
    while left <= right: 
     mid = (left+right) // 2 
     #increasing region 
     if arr[mid+1] > arr[mid] and arr[mid] > arr[mid-1]: 
      left = mid + 1 
     #decreasing region 
     elif arr[mid+1] < arr[mid] and arr[mid] < arr[mid-1]: 
      right = mid - 1 
     elif arr[mid+1] < arr[mid] and arr[mid-1] > arr[mid]: 
      return arr[mid-1] 
     else: 
      return arr[mid] 
    return -1