1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

//! Valid Perfect Square [leetcode: valid_perfect_square](https://leetcode.com/problems/valid-perfect-square/)
//!
//! Given a positive integer *num*, write a function which returns True if *num* is a perfect square else False.
//!
//! **Note: Do not** use any built-in library function such as `sqrt`.
//!
//! **Example 1:**
//! ```
//! Input: 16
//! Output: true
//! ```
//!
//! **Example 2:**
//! ```
//! Input: 14
//! Output: false
//! ```
//!
/// # Solutions
///
/// # Approach 1: Binary Search
///
/// * Time complexity: log(n)
///
/// * Space complexity: log(n)
///
/// * Runtime: 0 ms
/// * Memory: 2.4 MB
///
/// ```rust
/// impl Solution {
///     pub fn is_perfect_square(num: i32) -> bool {
///         if num == 0 { return false; }
///
///         let num = num as usize;
///         let mut left = 1 as usize;
///         let mut right = num;
///
///         while left <= right {
///             let mid = (right - left) / 2 as usize + left;
///             if mid * mid == num { return true; }
///             if mid * mid > num { right = mid - 1 as usize; } else { left = mid + 1 as usize; }
///         }
///
///         false
///     }
/// }
/// ```
///
pub fn is_perfect_square(num: i32) -> bool {
    if num == 0 { return false; }

    let num = num as usize;
    let mut left = 1 as usize;
    let mut right = num;

    while left <= right {
        let mid = (right - left) / 2 as usize + left;
        if mid * mid == num { return true; }
        if mid * mid > num { right = mid - 1 as usize; } else { left = mid + 1 as usize; }
    }

    false
}