Leetcode - Rust - Sum of square numbers using binary search

leetcode-rust-sum-of-square-numbers.rs

use std::{time::Instant};

fn main() {
    solution_sum_of_square_numbers_bs();
}

// Problem: https://leetcode.com/problems/sum-of-square-numbers/
// Solution: https://leetcode.com/problems/sum-of-square-numbers/solutions/4132153/rust-solution-using-binary-search/
// Sources:
// - https://www.geeksforgeeks.org/check-whether-number-can-represented-sum-two-squares/
// - Other answers
// - Medium difficulty
fn solution_sum_of_square_numbers_bs() {
    assert!(sum_of_square_numbers_bs(5));
    assert!(sum_of_square_numbers_bs(4));
    assert!(!sum_of_square_numbers_bs(3));
    assert!(sum_of_square_numbers_bs(100000));
    assert!(!sum_of_square_numbers_bs(999999999));
}

fn sum_of_square_numbers_bs(c: i32) -> bool {
    let timer = Instant::now();
    let fat_c: i64 = c as i64;
    let max_len: i64 = (c as f64).sqrt() as i64;
    let mut result: bool = false;

    let bs_mid = |start: i64| -> bool {
        let mut l: i64 = 0;
        let mut r: i64 = max_len;

        while l <= r {
            // Find mid 
            let mid: i64 = (l + r) / 2;
            let sum = (start * start) + (mid * mid);
            if sum == fat_c {
                // Found it
                return true;
            } else if sum > fat_c {
                // Overshoot, find the lower half
                r = mid - 1;
            } else {
                // Too short, find the higher half
                l = mid + 1;
            }
        }

        false
    };

    for x in 0..max_len + 1 {
        let fat_x = x as i64;
        if bs_mid(fat_x) {
            result = true;
        }
    }

    let duration = timer.elapsed().as_millis();
    println!("binary search: c={} in {} ms", c, duration);
    result
}