Использование алгоритма бинарного поиска для нахождения квадратного корня числа на 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/