Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java
Наткнулась на leetcode на задачку с нахождением квадратного корня из неотрицального числа.
Кажется, что для решения такой задачки отлично подходит бинарный поиск, который по итогу даст нам логарифмическую временную сложность.
Итак, условие задачи здесь: https://leetcode.com/problems/sqrtx/description/
Но прежде чем приступить к решению, пройдемся по теории, что такое бинарный поиск и как его использовать.
Бинарный поиск — это поисковый алгоритм, который позволяет найти элемент в отсортированном массиве с логарифмической сложностью. Массив делится пополам, искомый элемент сравнивается с серединой массива, если искомый элемент больше, то поиск переходит в правую часть массива, и наоборот. После каждого перехода в правую или левую часть будет происходить сравнение серединного элемента с искомым до тех пор, пока он не будет найден.
Акцентирую внимание еще раз: массив должен быть отсортирован по возрастанию.
Если массив не отсортирован, то сортировка потребует минимум O (log n * n) временной сложности, что нужно учитывать.
Поэтому, если массив небольшой и неупорядоченный, то, скорее всего, лучше будет линейный поиск со сложностью O (n).
Итак, теперь вернемся к нашей задачке. Нужно найти квадратный корень из неотрицательного числа, где само число может быть любым от 0 до 231 — 1. Если корень из числа извлекается с остатком, например, корень из 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 if (mid <= x / mid) {
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 (mid <= x / mid) {
left = mid + 1;
result = mid;
}
}
return result;
}Вот так можно использовать бинарный поиск для нахождения квадратного корня из числа. Если еще хотите попрактиковаться, то вот еще задачка уровня «Easy», где применяется тот же подход:
https://leetcode.com/problems/search-insert-position/description/
