바이너리 검색, 언제 높게 또는 낮게 늘려야합니까?

Question

낮은 값이나 높은 값을 증가시키는 방법을 이해하기가 어렵습니다. 예를 들어

,이 leetcode에서 질문 :

구현 INT SQRT (INT X).

내 코드 : 조건이 fufill 후 당신이 볼

class Solution { 
public: 
    int mySqrt(int x) { 
     if (x<=0) return 0; 
     int low=1, high=x, mid=0; 
     while (low<=high){   // should I do low<high? 
      mid=low+(high-low)/2; 
      if (x/mid==mid) return mid; 
      if (x/mid>mid) low= mid+1; //can I just do low=mid? 
      else   high=mid-1; // can I do high =mid? 

     } 
     return high; //after breaking the loop, should I return high or low? 

    } 
}; 

, 나는 low=mid 또는 low=mid+1을 설정할지 여부를 알 수 없습니다. 왜 mid+1일까요?

일반적으로 나는 중간 지점에서 낮게 증가해야하는지 아닌지 알아보기가 어렵습니다. 또한 또는 low < high을 while 루프에 포함시켜야 할 때도 문제가 있습니다.

Answer 1

귀하의 골동품은 이진 검색이 아닙니다. 또한 작동하지 않습니다.

예를 가지고 X = 5

Initial: 
low = 1, high = 5 

Iter 1: 
mid = 3 
5/3 = 1 so high = 4 

Iter 2: 
mid = 2.5 => 2 (because int) 
5/2 = 2 (because int) 

<returns 2> 

정사각형 입력를 들어, 너 한테 만 mid하지 high 또는 low를 통해 정확한 결과를 제공 할 것입니다.

인 경우 mid을 늘려야하고 그렇지 않은 경우 줄여야합니다. mid을 늘리거나 줄이는 방법은 각각 low으로 증가 시키거나 high을 줄입니다.

괜찮습니다.하지만 이진 검색이 아닙니다. high은 x에서 (2*sqrt - 1)까지의 모든 정수를 처리합니다.

훨씬 더 나은 솔루션

Answer 2

이 제곱근에 대한 Babylonian 방법에 @sinsuren 코멘트를 따르십시오 :

/*Returns the square root of n.*/ 
float squareRoot(float n) 
{ 
    /*We are using n itself as initial approximation 
    This can definitely be improved */ 
    float x = n; 
    float y = 1; 
    float e = 0.000001; /* e decides the accuracy level*/ 
    while(x - y > e) 
    { 
    x = (x + y)/2; 
    y = n/x; 
    } 
    return x; 
} 

더 이해를 위해 항상 따를 수 this link