Por que e como?

enquanto eu estava resolvendo a questão no leetcode que diz em uma determinada matriz de números inteiros classificados em ordem não decrescente, encontre a posição inicial e final de um determinado valor alvo. então era impossível retornar o início e o fim de um elemento alvo em um array com scarch binário simples porque ele retorna apenas o índice onde encontrou o primeiro elemento alvo que pode ser qualquer coisa primeiro, final ou meio desse elemento. então usamos Double Binary Scarch e veja como fazer isso ...

Abordagem

1. Primeira pesquisa binária:

   • Realize uma pesquisa binária para encontrar a última ocorrência do alvo.
   • Comece com si (índice inicial) em 0 e ei (índice final) em nums.length - 1.
   • Se o elemento do meio nums[mid] for menor que o alvo, mova o índice inicial si para mid 1 para pesquisar na metade direita.
   • Se for maior que o alvo, mova o índice final ei para mid - 1 para pesquisar na metade esquerda.
   • Se nums[mid] for igual ao alvo, defina res[1] como mid (o final atual do intervalo) e continue pesquisando na metade direita (si = mid 1) para encontrar a última ocorrência.

2. Segunda pesquisa binária:

   • Realize outra pesquisa binária para encontrar a primeira ocorrência do alvo.
   • Redefinir si para 0 e ei para nums.length - 1.
   • Siga uma abordagem semelhante à anterior, mas se nums[mid] for igual ao alvo, defina res[0] como mid (o início atual do intervalo) e continue pesquisando na metade esquerda (ei = mid - 1) para encontre a primeira ocorrência.

3. Resultado do retorno:

   • A matriz de resultados res contém os índices inicial e final do valor alvo.

Complexidade

• Complexidade de tempo:

  • A pesquisa binária para a primeira e a última ocorrência leva tempo O (log n). Como realizamos duas pesquisas binárias, a complexidade geral do tempo é O(log n).

• Complexidade espacial:

  • O(1) já que estamos usando uma quantidade fixa de espaço extra para variáveis.

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
    }
}