Блог

Главная - Вопросы по программированию - Бинарный поиск, когда мне следует увеличить значение high или low?

Бинарный поиск, когда мне следует увеличить значение high или low?

#binary-search

#двоичный поиск

Вопрос:

Мне трудно понять, как увеличить значение low или high.

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

Реализуйте int sqrt(int x).

Мой код:

 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 со средней точки или нет. У меня также возникают проблемы, когда я должен включать low <= high or low < high в while цикл.

Комментарии:

1. if (x / mid ==mid) возвращает значение mid; здесь вы проверяете значение mid как квадратный корень, если это так, то оно возвращается отсюда. поэтому мы склонны не проверять это снова. Итак, мы делаем low = mid 1 и high = mid -1

2. И с помощью этого метода вы не получите квадратный корень из любого числа, за исключением нескольких случаев.

3. Читайте здесь. Надеюсь, это развеет все ваши сомнения. geeksforgeeks.org/square-root-of-a-perfect-square

Ответ №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 not high или low .

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

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

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

Ответ №2:

Это вавилонский метод получения квадратного корня:

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

Для более глубокого понимания вы всегда можете перейти по этой ссылке