¿Por qué y cómo?

mientras resolvía la pregunta sobre leetcode que dice en una matriz dada de números enteros ordenados en orden no decreciente, encuentre la posición inicial y final de un valor objetivo determinado. por lo que fue imposible devolver el inicio y el final de un elemento de destino en una matriz con un simple escaneo binario porque solo devuelve el índice donde encontró el primer elemento de destino que puede ser cualquier cosa primero, final o medio de ese elemento. entonces usamos Double Binary Scarch y aquí se explica cómo hacerlo...

Acercarse

1. Primera búsqueda binaria:

   • Realice una búsqueda binaria para encontrar la última aparición del objetivo.
   • Comience con si (índice inicial) en 0 y ei (índice final) en nums.length - 1.
   • Si el elemento central nums[mid] es menor que el objetivo, mueva el índice inicial si a mid 1 para buscar en la mitad derecha.
   • Si es mayor que el objetivo, mueva el índice final ei a mitad - 1 para buscar en la mitad izquierda.
   • Si nums[mid] es igual al objetivo, establezca res[1] en mid (el final actual del rango) y continúe buscando en la mitad derecha (si = mid 1) para encontrar la última aparición.

2. Segunda búsqueda binaria:

   • Realice otra búsqueda binaria para encontrar la primera aparición del objetivo.
   • Restablecer si a 0 y ei a nums.length - 1.
   • Siga un enfoque similar al anterior, pero si nums[mid] es igual al objetivo, establezca res[0] en mid (el inicio actual del rango) y continúe buscando en la mitad izquierda (ei = mid - 1) para encontrar la primera aparición.

3. Devolver resultado:

   • La matriz de resultados res contiene los índices inicial y final del valor objetivo.

Complejidad

• Complejidad del tiempo:

  • La búsqueda binaria de la primera y la última ocurrencia toma cada una de O(log n) tiempo. Dado que realizamos dos búsquedas binarias, la complejidad temporal general es O(log n).

• Complejidad espacial:

  • O(1) ya que estamos usando una cantidad fija de espacio adicional para las variables.

Código

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int ei = nums.length - 1;
        int si = 0;
        int[] res = {-1, -1};  // Initialize result array

        // First binary search to find the last occurrence
        while (si  nums[mid]) {
                si = mid   1;
            } else {
                res[1] = mid;  // Update end index
                si = mid   1;  // Search in the right half
            }
        }

        // Reset the pointers for the second binary search
        si = 0;
        ei = nums.length - 1;

        // Second binary search to find the first occurrence
        while (si  nums[mid]) {
                si = mid   1;
            } else {
                res[0] = mid;  // Update start index
                ei = mid - 1;  // Search in the left half
            }
        }

        return res;  // Return the result array
    }
}