Двоичный поиск для квадратного корня [домашняя работа]

Question

Для назначения я должен создать метод, используя двоичный поиск, чтобы найти квадратный корень из целого числа, и если он не является квадратным числом, он должен возвращать целое число s такое, что s * s < = номер (поэтому для 15 он вернется 3). Код у меня есть для него до сих пор

public class BinarySearch { 

    /** 
    * Integer square root Calculates the integer part of the square root of n, 
    * i.e. integer s such that s*s <= n and (s+1)*(s+1) > n 
    * requires n >= 0 
    * 
    * @param n number to find the square root of 
    * @return integer part of its square root 
    */ 
    private static int iSqrt(int n) { 
     int l = 0; 
     int r = n; 
     int m = ((l + r + 1)/2); 

     // loop invariant 
     while (Math.abs(m * m - n) > 0) { 
      if ((m) * (m) > n) { 
       r = m; 
       m = ((l + r + 1)/2); 
      } else { 
       l = m; 
       m = ((l + r + 1)/2); 
      } 
     } 
     return m; 
    } 

    public static void main(String[] args) { 
     //gets stuck 
     System.out.println(iSqrt(15)); 
     //calculates correctly 
     System.out.println(iSqrt(16)); 
    } 
} 

И это возвращает правильный номер для квадратных чисел, но получает палку в бесконечном цикле для других чисел. Я знаю, что проблема заключается в условии while, но я не могу понять, что из-за разрыва между квадратными цифрами становится намного больше, поскольку числа становятся больше (поэтому я не могу просто сказать, что разрыв должен быть ниже порог). Это упражнение касается инвариантов, если это помогает вообще (поэтому почему оно настроено таким образом). Спасибо.

Answer 1

Подумайте об этом: Math.abs(m*m-n) > 0 всегда является истинным неквадратичным числом, потому что он никогда не равен нулю, а .abs не может быть отрицательным. Это ваше условие цикла, поэтому цикл никогда не заканчивается.

Означает ли это, что вы хотите получить информацию?

Answer 2

Вам необходимо изменить while (Math.abs(m * m - n) > 0), чтобы обеспечить допустимый предел погрешности, вместо того чтобы требовать от него ровно равного нулю, как и сейчас.

Попробуйте while((m+1)*(m+1) <= n || n < m * m)

Answer 3

Как Кен Блум сказал, что вы должны иметь Мардж ошибки, 1. Я тестировал этот код и он работает, как ожидался на 15. Кроме того, вы должны будете использовать поплавок, я думаю, что это алгоритм не представляется возможным для INT (хотя у меня нет математического доказательства)

private static int iSqrt(int n){ 
float l = 0; 
float r = n; 
float m = ((l + r)/2); 


while (Math.abs(m*m-n) > 0.1) { 
    if ((m)*(m) > n) { 
     r=m; 
     System.out.println("r becomes: "+r); 


    } else { 
     l = m; 
     System.out.println("l becomes: "+l); 

    } 
    m = ((l + r)/2); 
    System.out.println("m becomes: "+m); 
} 

return (int)m; 

} 

Answer 4

#define EPSILON 0.0000001 
double msqrt(double n){ 
    assert(n >= 0); 
    if(n == 0 || n == 1){ 
     return n; 
    } 
    double low = 1, high = n; 
    double mid = (low+high)/2.0; 
    while(abs(mid*mid - n) > EPSILON){ 
     mid = (low+high)/2.0; 
     if(mid*mid < n){ 
      low = mid+1; 
     }else{ 
      high = mid-1; 
     } 
    } 
return mid;} 

Как вы можете видеть выше, вы должны просто применить бинарный поиск (метод бисекции) и вы можете свести к минимуму Epsilon, чтобы получить более точным результатов, но потребуется больше времени t o запустить. Редактировать: Я написал код в C++ (извините)