Двоичный поиск, когда я должен увеличивать или понижать?

Question

Мне сложно понять, как увеличить или понизить уровень.

Например, это вопрос из leetcode:

Реализовать INT SQRT (INT х).

Мой код:

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? 

    } 
}; 

Вы видите, после того, как условие fufill, я не знаю, должен ли я установить low=mid ИЛИ low=mid+1. Почему mid+1?

В общем, у меня возникли проблемы с тем, следует ли мне увеличивать низкий уровень с середины или нет. У меня также возникают проблемы, когда я должен включать low <= high или low < high в петлю while.

Answer 1

Ваше алго не является бинарным поиском. Кроме того, он не работает.

Возьмем пример х = 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.

BTW вам нужно увеличить mid, если x/mid > mid, и вам нужно уменьшить его в противном случае. Ваш метод увеличения и уменьшения mid увеличивается на low или уменьшает high соответственно.

Это нормально, но это не дает двоичного поиска. Ваш high будет проходить через все целые числа от x до (2*sqrt - 1).

Пожалуйста, следуйте @sinsuren комментарий к гораздо лучшее решение

Answer 2

Это Babylonian метод квадратного корня:

/*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