Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java

Наткнулась на leetcode на задачку с нахождением квадратного корня из неотрицального числа.

Кажется, что для решения такой задачки отлично подходит бинарный поиск, который по итогу даст нам логарифмическую временную сложность. 

Итак, условие задачи здесь: https://leetcode.com/problems/sqrtx/description/

Но прежде чем приступить к решению, пройдемся по теории, что такое бинарный поиск и как его использовать.

Бинарный поиск - это поисковый алгоритм, который позволяет найти элемент в отсортированном массиве с логарифмической сложностью. Массив делится пополам, искомый элемент сравнивается с серединой массива, если искомый элемент больше, то поиск переходит в правую часть массива, и наоборот. После каждого перехода в правую или левую часть будет происходить сравнение серединного элемента с искомым до тех пор, пока он не будет найден.

Акцентирую внимание еще раз: массив должен быть отсортирован по возрастанию.

Если массив не отсортирован, то сортировка потребует минимум O(log n * n) временной сложности, что нужно учитывать.

Поэтому, если массив небольшой и неупорядоченный, то, скорее всего, лучше будет линейный поиск со сложностью O(n).

Итак, теперь вернемся к нашей задачке. Нужно найти квадратный корень из неотрицательного числа, где само число может быть любым от 0 до 2³¹ - 1. Использовать встроенные функции при этом нельзя, так что return (int) Math.sqrt(x) не подойдет (хотя leetcode ее примет). Если корень из числа извлекается с остатком, например, корень из 8 это 2.82842…, то нужно округлить в меньшую сторону до целого, т.е. в данном случае до 2.

Начнем, по порядку, ограничив краевые случаи. Так, если х = 0, то можно сразу вернуть 0.

if (x == 0) {

    return 0;

}

Дальше зададим границы, левую и правую. Левая граница в данном случае - это 1, а правая само число Х. Также нам понадобиться переменная, в которую мы запишем результат:

int left = 1;

int right = x;

int result = 0;

Мы будем выполнять поиск нужного нам элемента, пока левая граница (left) будет меньше или равна правой (right), если левая граница станет больше, то значит результат уже был найден и нужно его возвращать.

while (left <= right) {
  //тут будет алгоритм
}

Внутри самого цикла while мы будем двигать границы, согласна правилу выше. Сначала найдем середину: 

while (left <= right) {
  int mid = left + (right - left) / 2;
  ...
}    

Если значение серединного элемента больше, чем заданное число деленное на серединный элемент, то надо двигать правую границу, иначе левую, и записывать промежуточный результат:

while (left <= right) {
  int mid = left + (right - left) / 2;
  if (mid > x / mid) {
    right = mid - 1;
  } else {
    left = mid + 1;
    result = mid;
  }
}

Допустим, заданное число - это 18. Тогда left = 1, right = 18,  заходим в цикл, так как 1 < 18 (left <=right), находим mid = 1 + (18 - 1) / 2 = 9. Проверяем условие: 9 > 18 / 9, поэтому двигаем правую границу влево: right = 9 - 1 = 8.

Снова проверяем условие 1 < 8 (left <=right), входим в цикл, находим середину: mid = 1 + (8 - 1) / 2 = 4. Рассчитываем x / mid - это 18 / 4 ≈ 4, значит mid = x / mid ( 4 ≈ 18 / 4 ), значит left = 5, result = 4 (подвинули границы вправо)

Так как условие, left <= right все еще выполняется, мы снова зайдем в цикл (хотя на самом деле мы уже нашли нужный result для нашего конкретного примера), снова рассчитаем mid = 5 + (8 - 5) / 2 ≈ 6, вычислим x / mid = 18 / 6 = 3,  попадем в условие mid > x / mid,  так как 6 > 3, пересчитаем right = 6 - 1 = 5. Снова зайдем в цикл, и выйдем уже на следующем пересчете right, когда right будет равно 4, а left останется без изменений. После этого будет возвращен результат.

Фиксируем полный метод для решения задачи:

public int mySqrt(int x) {
  if (x == 0) {
    return 0;
  }
  int left = 1;
  int right = x;
  int result = 0;
  while (left <= right) {
    int mid = left + (right - left) / 2;
    if (mid > x / mid) {
       right = mid - 1;
    } else if {
       left = mid + 1;
       result = mid;
    }
  }
  return result;
}

Вот так можно использовать бинарный поиск для нахождения квадратного корня из числа. Если еще хотите попрактиковаться, то вот еще задачка уровня «Easy», где применяется тот же подход: 

https://leetcode.com/problems/search-insert-position/description/

Кстати, сделала свой телеграм-канал, где пишу подходы к решениям всяких задачек с LeetCode, там будет больше разборов конкретных задач, чем здесь, потому что не всегда нужна статья. В общем, если интересно - жду здесь - t.me/crushiteasy :)