title: Binary search for square root [homework]
body: <p>For an assignment I must create a method using a binary search to find the square root of an integer, and if it is not a square number, it should return an integer s such that s*s &lt;= the number (so for 15 it would return 3). The code I have for it so far is</p>
  
  <pre><code>public class BinarySearch {
  
      /**
       * Integer square root Calculates the integer part of the square root of n,
       * i.e. integer s such that s*s &lt;= n and (s+1)*(s+1) &gt; n
       * requires n &gt;= 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) &gt; 0) {
              if ((m) * (m) &gt; 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));
      }
  }
  </code></pre>
  
  <p>And this returns the right number for square numbers, but gets stick in an endless loop for other integers. I know that the problem lies in the while condition, but I can't work out what to put due to the gap between square numbers getting much bigger as the numbers get bigger (so i can't just put that the gap must be below a threshold). The exercise is about invariants if that helps at all (hence why it is set up in this way). Thank you.</p>