从leetcode oj中二分搜索平方根

Question

public static int sqrt(int x) {

     if( x == 0 || x == 1){
         return x;
     }
     long start = 0;
     long end = x;


     while ( end-start > 1){
         long mid = (int)(end + start) / 2;
         long s = mid * mid;

         if(s == x){
             return (int)mid;
         }
         else if(s > x){
             end = mid;
         }
         else {
             start = mid;
         }

     }

     return (int)start;
    }

上面是工作代码段。我有以下问题。事先谢谢你的帮助。；-）

1. while(end-start>1)为什么这里需要1？就因为返回的意思是int？
2. 如果我们将while循环从while(end-start>1)更改为while(end>start)，我们必须使end=mid-1；和start=mid+1,对吗？还有一步，不知道这是不是也是因为返回类型是整数？
3. 为什么不能返回End？或（int）（开始+结束）/2？？我看到几乎99%的答案都回到了二分搜索的左界。我只想知道回到右边边界还是中间边界好？

Answer 1

返回类型int只是表示返回的结果类型为int。它与方法体内部的算法无关。下面我试着回答你的问题：

1. while(end-start>1)用于确保end始终大于start。如果end-start为1或小于1，则表示您已到达二进制搜索的结尾。
2. 您可以继续将while(end-start>1)更改为while(end>start)，它仍然可以工作。不必使end=mid-1和start=mid+1。
3. 这完全取决于你在哪里回答谎言。对于每个问题，它可能是不同的。

您应该尝试下面的链接来更好地理解二分搜索算法。

http://community.topcoder.com/tc？module=static&d1=tutorials&d2=binarysearch

希望有帮助。