Sqrt(x)

class Solution:
    def mySqrt(self, x: int) -> int:
        # エッジケース: x=0, x=1 は即リターン
        if x < 2:
            return x

        # 探索範囲: [1, x // 2]
        # 根拠: x >= 2 のとき floor(√x) <= x // 2 が常に成立
        low: int = 1
        high: int = x >> 1  # ビットシフトで x // 2（CPython 最速）

        # Loop Invariant:
        #   (low - 1)^2 <= x  かつ  (high + 1)^2 > x
        # → ループ終了時: high = floor(√x)
        while low <= high:
            mid: int = (low + high) >> 1  # 中点計算
            sq:  int = mid * mid          # Python int は任意精度 → オーバーフローなし

            if sq == x:
                return mid       # 完全平方数: 即リターン
            elif sq < x:
                low = mid + 1    # mid が小さすぎる → 下限を引き上げ
            else:
                high = mid - 1   # mid が大きすぎる → 上限を引き下げ

        # ループ終了後: high = floor(√x)
        return high

function mySqrt(x: number): number {
    // エッジケース: x=0, x=1 は即リターン
    if (x < 2) return x;

    // 探索範囲: [1, x >>> 1]
    let low: number = 1;
    let high: number = x >>> 1;  // x / 2（符号なし右シフト整数除算）

    // Loop Invariant:
    //   low  - 1 の二乗は x 以下
    //   high + 1 の二乗は x より大きい
    while (low <= high) {
        const mid: number = (low + high) >>> 1;  // 符号なし右シフトで安全な中点計算
        const square: number = mid * mid;

        if (square === x) {
            return mid;           // 完全平方数
        } else if (square < x) {
            low = mid + 1;        // 下限を引き上げ
        } else {
            high = mid - 1;       // 上限を引き下げ
        }
    }

    // ループ終了後: high = floor(√x)
    return high;
}

impl Solution {
    pub fn my_sqrt(x: i32) -> i32 {
        debug_assert!(x >= 0, "x must be non-negative, got {x}");
        let x = x as u32;

        // エッジケース: x=0, x=1 は即リターン
        if x < 2 { return x as i32; }

        // 探索範囲: [1, x >> 1]
        let mut low: u32 = 1;
        let mut high: u32 = x >> 1;

        // Loop Invariant:
        //   (low - 1)^2 <= x  かつ  (high + 1)^2 > x
        while low <= high {
            let mid: u32 = low + (high - low) / 2;  // オーバーフロー安全な中点計算
            let square: u64 = (mid as u64) * (mid as u64);  // u64 昇格でオーバーフロー防止
            let target: u64 = x as u64;

            match square.cmp(&target) {
                std::cmp::Ordering::Equal   => return mid as i32,  // 完全平方数
                std::cmp::Ordering::Less    => low  = mid + 1,     // 下限を引き上げ
                std::cmp::Ordering::Greater => high = mid - 1,     // 上限を引き下げ
            }
        }

        high as i32  // ループ終了後: high = floor(√x)
    }
}