Resumen
parcialmente comprobar si la matriz está ordenada de modo que la búsqueda binaria es aplicable se puede hacer en O (log n), como dijo el OP, y en O (1). El método O (log n) es verificar cada una de las sondas con la sonda anterior para asegurarse de que se compare adecuadamente (menor que, mayor que). El método O (1) consiste simplemente en comprobar el elemento final encontrado por la búsqueda binaria y el siguiente junto a él, de modo que si no se encuentra el elemento buscado, al menos se encontró el lugar correcto para la inserción. Si se encontró el elemento buscado, entonces esa es una buena O (1) verificación parcial.
más larga explicación
La parte del problema antes de que el bloque de código dice que un problema común es mediante la búsqueda binaria en un array sin clasificar. Básicamente, ¿cómo se puede utilizar la comprobación parcial para verificar si una matriz se ordena en menos de O (n-1) costo?
La solución O (log n) consiste en comprobar cada una de las sondas de búsqueda binarias con respecto a la sonda anterior (es menor o mayor de lo que se espera que sea). Esto no garantiza que la matriz esté ordenada, pero es una buena verificación parcial.
La única verificación O (1) que puedo pensar es comprobar el lugar final que se busca de modo que su valor y los valores vecinos se combinen con la idea de dónde debe estar el elemento buscado, incluso si el elemento no fue encontrado. Es una comprobación parcial bastante buena: si se encuentra el elemento, probablemente las cosas funcionen correctamente. Si no fuera así, compruebe los elementos alrededor de donde debería estar, de manera que haya un elemento menos que el buscado y luego uno que sea mayor que el elemento buscado. Sin embargo, me doy cuenta de que al comprobar de esta manera, significa que la búsqueda binaria, que es O (log n), ya se ha realizado, así que no sé si realmente es O (1). Sin embargo, solo agrega O (1) a la búsqueda general, por lo que creo que es aplicable.
¿Un poco más elaborado? – pavanlimo