Square Root (Integer)

Q: Qual é a complexidade de tempo da raiz quadrada por busca binária?

Tempo O(log x) e espaço O(1) . Cada etapa reduz pela metade o intervalo de candidatos, então x = 2^31 - 1 precisa de 31 etapas. Contar a partir de 0 leva O(√x) etapas, 46340 para o mesmo x , o que é aceitável aqui, mas cresce rapidamente com entradas de 64 bits.

Q: Como o método de Newton calcula uma raiz quadrada inteira?

Comece com r = x . Enquanto r × r > x , substitua r por (r + x / r) / 2 usando divisão inteira. Cada etapa aproxima r da raiz por baixo, sem ultrapassá-la, e o loop para no piso da raiz quadrada. Para x = 2^31 - 1 , são necessárias 19 etapas, e o número de dígitos corretos aproximadamente dobra a cada etapa quando o valor já está próximo.

FácilBusca binária Matemática e simulação

+10

Sua função recebe um número inteiro não negativo x e retorna sua raiz quadrada inteira: o maior número inteiro r tal que r × r ≤ x. Ou seja, a raiz quadrada arredondada para baixo; assim, um número que não é um quadrado perfeito recebe a raiz do quadrado perfeito imediatamente inferior. Calcule-a você mesmo, sem usar uma função integrada de raiz quadrada ou potência.

Função

mySqrt(x: integer) → integer

xinteger: o inteiro não negativo do qual calcular a raiz quadrada
Retornainteger: a raiz quadrada de x arredondada para baixo até um número inteiro

Restrições

0 ≤ x ≤ 2³¹ - 1
Não chame uma função integrada de raiz quadrada, potência ou exponenciação.

Exemplos

Entrada: x = 17
Saída: 4
Explicação: 4 × 4 = 16 é no máximo 17, mas 5 × 5 = 25 é maior, então a raiz de 17 é arredondada para baixo, para 4.

Entrada: x = 49
Saída: 7
Explicação: 49 é um quadrado perfeito, 7 × 7 = 49, então nada é arredondado e a resposta é exatamente 7.

+17 testes ocultos ao enviar

Para ir além

Como você encontraria, em vez disso, a raiz cúbica inteira, o maior r tal que r × r × r ≤ x, se x também pudesse ser negativo?

Dicas

Abra uma de cada vez. Cada uma revela um pouco mais.

0 de 3 abertas

Solução

Contar a partir de 0 até que o próximo quadrado ultrapasse x dá a resposta certa, mas isso leva um passo por unidade da raiz, cerca de 46000 passos perto do limite superior do intervalo. Os quadrados 0, 1, 4, 9, 16 e assim por diante estão ordenados, então você pode fazer uma busca binária pelo último candidato cujo quadrado seja menor ou igual a x e terminar em cerca de 31 passos. O problema em ambos os casos é o overflow: o quadrado de um candidato nem sempre cabe em 32 bits.

Conte a partir de zero

Intuição

A raiz é o maior r tal que r × r ≤ x. Comece em r = 0, cujo quadrado sempre cabe, e continue avançando para r + 1 enquanto o quadrado do próximo número ainda couber. O loop para no primeiro r cujo sucessor é grande demais, que é exatamente a raiz. Para x = 17, os quadrados 1, 4, 9 e 16 cabem, e 25 não, então o loop para em 4.

O loop é executado uma vez por unidade da resposta. A maior resposta aqui é 46340, então são no máximo 46340 passos, o que termina rápido. O custo, porém, é O(√x) e cresce com a entrada: um x de 64 bits pode levar cerca de 3 × 10^9 passos.

Preste atenção à última verificação. Para x = 2^31 - 1, o loop eleva 46341 ao quadrado para descobrir que é grande demais, e 46341 × 46341 = 2147488281 não cabe em um inteiro de 32 bits. Faça a multiplicação em 64 bits.

Algoritmo

Defina root = 0.
Enquanto (root + 1) × (root + 1) ≤ x, aumente root em 1.
Retorne root.

def mySqrt(x):
    root = 0
    while (root + 1) * (root + 1) <= x:
        root += 1
    return root

Busca binária na resposta

Intuição

Alinhe os candidatos 0, 1, 2, até x, e faça a mesma pergunta a cada um: seu quadrado é menor ou igual a x? As respostas são sim, sim, sim e, em seguida, não para todos os candidatos após a raiz, porque os quadrados só aumentam. A raiz é o último sim. Uma sequência ordenada de sims seguida de nãos é exatamente para isso que a busca binária serve.

Mantenha o intervalo de lo a hi dos candidatos ainda não decididos, começando em 0 e indo até x, e uma variável best para o maior sim até então. Teste o meio mid. Se mid × mid ≤ x, a raiz é mid ou maior: armazene-o em best e mova lo para mid + 1. Caso contrário, a raiz é menor: mova hi para mid - 1. Quando o intervalo estiver vazio, best será a raiz.

Rastreie x = 17. O intervalo de 0 a 17 testa 8 (64, grande demais), depois de 0 a 7 testa 3 (9, cabe, best = 3), depois de 4 a 7 testa 5 (25, grande demais) e, por fim, de 4 a 4 testa 4 (16, cabe, best = 4). O intervalo fica vazio e a resposta é 4. Cada etapa reduz o intervalo pela metade, então x = 2^31 - 1 leva 31 etapas. Faça a multiplicação em 64 bits: o primeiro mid nesse caso é 1073741823.

Algoritmo

Defina lo = 0, hi = x e best = 0.
Enquanto lo ≤ hi, calcule mid, o meio do intervalo.
Se mid × mid ≤ x (em 64 bits), defina best = mid e lo = mid + 1.
Caso contrário, defina hi = mid - 1.
Retorne best.

def mySqrt(x):
    lo, hi = 0, x
    best = 0  # largest candidate seen so far whose square fits
    while lo <= hi:
        mid = (lo + hi) // 2
        if mid * mid <= x:
            best = mid  # mid fits, so try a larger root
            lo = mid + 1
        else:
            hi = mid - 1  # mid is too big
    return best

Armadilhas e casos extremos

A busca em si é curta; os bugs ficam escondidos na aritmética e nos casos extremos.

Elevar ao quadrado em 32 bits. Para x = 2147483647, o primeiro candidato a ponto médio é 1073741823, e seu quadrado é cerca de 1.15 × 10^18. Em um int de 32 bits, esse valor sofre overflow e se transforma em um valor incorreto, que pode até parecer pequeno o bastante para caber. Faça a multiplicação em 64 bits ou compare m ≤ x / m.
Elevar ao quadrado o próximo candidato em 32 bits no loop de contagem. A raiz de 2^31 - 1 é 46340, e a última verificação do loop eleva 46341 ao quadrado, resultando em 2147488281, acima do limite de 32 bits.
Levar o intervalo além dos 32 bits. Um limite exclusivo hi = x + 1 é 2147483648 para o maior valor de x, ultrapassando em 1 o limite de 32 bits. Com o hi = x inclusivo, lo + hi chega exatamente a 2147483647 na primeira etapa, então cabe sem margem de sobra. Use índices de 64 bits ou lo + (hi - lo) / 2.
Retornar o último mid que você verificou em vez do último que se encaixava. Para x = 17, a busca termina depois de testar 5, que é grande demais; a resposta é o 4 armazenado.
Quebrar os casos pequenos. Uma busca que começa em lo = 1 não encontra x = 0, e a verificação de divisão m ≤ x / m divide por zero quando m = 0. Teste 0 e 1 separadamente.

Perguntas frequentes4

Como encontrar uma raiz quadrada sem uma função integrada?

Para calcular a raiz quadrada inteira, faça uma busca binária pela resposta. Os candidatos de 0 a x se dividem em uma sequência cujos quadrados são menores ou iguais a x e outra cujos quadrados são maiores; a busca binária encontra o último candidato da primeira sequência. O método de Newton é a outra resposta comum: ele refina uma estimativa r com (r + x / r) / 2 até que o quadrado seja adequado.

Qual é a complexidade de tempo da raiz quadrada por busca binária?

Tempo O(log x) e espaço O(1). Cada etapa reduz pela metade o intervalo de candidatos, então x = 2^31 - 1 precisa de 31 etapas. Contar a partir de 0 leva O(√x) etapas, 46340 para o mesmo x, o que é aceitável aqui, mas cresce rapidamente com entradas de 64 bits.

Como o método de Newton calcula uma raiz quadrada inteira?

Comece com r = x. Enquanto r × r > x, substitua r por (r + x / r) / 2 usando divisão inteira. Cada etapa aproxima r da raiz por baixo, sem ultrapassá-la, e o loop para no piso da raiz quadrada. Para x = 2^31 - 1, são necessárias 19 etapas, e o número de dígitos corretos aproximadamente dobra a cada etapa quando o valor já está próximo.

Por que a solução precisa de inteiros de 64 bits quando a resposta cabe em 32 bits?

A resposta é no máximo 46340, mas os candidatos testados não são. A busca binária entre 0 e x primeiro testa um candidato próximo de 10^9, e seu quadrado é próximo de 10^18, muito além do limite de 32 bits, de cerca de 2.1 × 10^9. Elevar ao quadrado usando 64 bits mantém a comparação exata. Comparar m ≤ x / m evita totalmente o produto grande.

Python

def mySqrt(x):
    # Escreva o código aqui

Casos de teste

Caso 1

Caso 2

Entrada

x = 17

Esperado