69.sqrtx.md

問題

https://leetcode.com/problems/sqrtx/

回答

初回の回答: 1..x の間の整数で二分探索する

x の累乗根の整数部分を返す問題。x は最大 $2^{31}-1$ にもなるので、1..x を全件なめていたらとんでもない時間がかかる。ということで計算量を $\mathcal{O}(\log{_2}n)$ に減らすために二分探索をする。

$[1, 2, 3, 4, ..., x-2, x-1, x]$という配列があったとして、どれかは x の累乗根の整数部分になるはず。ただ、累乗根と整数を比較するのは難しいので全要素を二乗してしまう。

$$ \begin{aligned} & [1, 2, 3, 4, ..., x-2, x-1, x] \\ & \downarrow \\ & [1, 4, 9, 16, ..., (x-2)^2, (x-1^2), x^2] \end{aligned} $$

この配列を二分探索して、middle の値が

• ちょうど整数部分と一致すればそのままその整数を返す（ex. $x=9$ のときの $3$ など）
• 最後までヒットしなかった場合、少なくとも middle - 1 の整数よりは大きいので middle - 1 を返す（ex. $x=6$ のときの $2$ など）

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        if x < 2 {
            return x;
        };
        let mut left = 1;
        let mut right = x as i64;
        let mut middle = (x / 2) as i64;
        while left < right {
            match (middle * middle).cmp(&(x as i64)) {
                std::cmp::Ordering::Equal => return middle as i32,
                std::cmp::Ordering::Greater => {
                    right = middle;
                    middle = (left + right) / 2;
                }
                std::cmp::Ordering::Less => {
                    left = middle + 1;
                    middle = (left + right) / 2;
                }
            }
        }
        (right - 1) as i32
    }
}