Límite más bajo teórico de la búsqueda de ocurrencias de un entero objetivo en una matriz ordenada

Question

Dada una matriz ordenada de enteros y un entero objetivo, encuentre el número de ocurrencias del entero objetivo.

Es bien sabido que una búsqueda binaria tiene complejidad de tiempo $ o (\ lg n) $ donde $ n$ es el tamaño de la matriz. Por ejemplo, dado una matriz $ [1,2,3,3,4,5] $ y un objetivo $ 3,$ El algoritmo debe devolver $ 2 $ ya que hay dos copias de $ 3 $ en la matriz.

Pregunta: ¿Hay algún algoritmo más rápido que tenga la complejidad del tiempo menor que $ o (\ lg n)? $ de lo contrario, hay una prueba para demostrar que $ \ omega (\ lg n) $ es el límite inferior teórico?

Answer 1

El problema requiere $ \ omega (\ log n) $ acceda a la memoria incluso si se le prometió que el entero objetivo aparece como máximo una vez. Puede probarlo usando un argumento de adversario.

Di que el objetivo es cero. Si el primer acceso a la matriz se encuentra en el centro, responda $ - 1 $ y configura mentalmente los elementos a la izquierda para ser $ - 2, -3, \ ldots $ . Si el primer acceso está en el centro del centro, responda $ + 1 $ y configura mentalmente los elementos a la derecha para ser $ 2 , 3, \ ldots $ .

Supongamos que el primer acceso fue el derecho del centro, digamos la posición $ i $ , y considere el segundo acceso. Si lo es a la derecha del primer acceso, entonces ya sabes qué responder. De lo contrario, hay dos casos. Si la posición Accedida $ J $ es menos que $ i / 2 $ , responda $ - 1 $ (y rellene los elementos a la izquierda). Si fue más de $ i / 2 $ , responda $ + 1/2 $ (y complete Elementos a la derecha hasta la posición $ i $ ).

Continuando de esta manera, en cada paso, el número de posiciones que podrían contener el elemento objetivo se reduce a la mitad en cada paso. Finalmente, cuando solo un elemento todavía está en juego, sin consultarlo, el algoritmo no puede saber seguro si la matriz contiene el elemento objetivo o no. Se necesita $ \ log_2 n $ pasos para llegar a este paso.

Lo anterior muestra que la búsqueda binaria es óptima para buscar una matriz ordenada.

Answer 2

Hay $ n $ Posibles respuestas.Cada comparación le da como máximo un poco de información.Necesita al menos $ \ lg n $ bits de información para describir la respuesta, por lo que necesitará al menos $ \LG n $ comparaciones.