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