Использование алгоритма бинарного поиска для нахождения квадратного корня числа на Java
Наткнулась на leetcode на задачку с нахождением квадратного корня из неотрицального числа. Кажется, что для решения такой задачки отлично подходит бинарный поиск, который по итогу даст нам логарифмическую временную сложность. Итак, условие задачи здесь: https://leetcode.com/problems/sqrtx/description/ Но прежде чем приступить к решению, пройдемся по теории, что такое бинарный поиск и как его использовать. Бинарный поиск - это поисковый алгоритм, который позволяет найти элемент в отсортированном массиве с логарифмической сложностью . Массив делится пополам, искомый элемент сравнивается с серединой массива, если искомый элемент больше, то поиск переходит в правую часть массива, и наоборот. После каждого перехода в правую или левую часть будет происходить сравнение серединного элемента с искомым до тех пор, пока он не будет найден. Акцентирую внимание еще раз: массив должен быть отсортирован по возрастанию. Если массив не отсортирован, то сортировка потребует минимум O(log n * n) временной сложности, что нужно учитывать. Поэтому, если массив небольшой и неупорядоченный, то, скорее всего, лучше будет линейный поиск со сложностью O(n). Итак, теперь вернемся к нашей задачке. Нужно найти квадратный корень из неотрицательного числа, где само число может быть любым от 0 до 2 31 - 1. Если корень из числа извлекается с остатком, например, корень из 8 это 2.82842…, то нужно округлить в меньшую сторону до целого, т.е. в данном случае до 2. Начнем, по порядку, ограничив краевые случаи. Так, если х = 0, то можно сразу вернуть 0.
https://habr.com/ru/articles/832212/
#алгоритмы #алгоритмы_поиска #программирование #разработка #java #бинарный_поиск #подготовка_к_собеседованиям
