---
# System prepended metadata

title: Binary search
tags: [練習題]

---

###### tags: `練習題`

# Binary search
## [367. Valid Perfect Square](https://leetcode.com/problems/valid-perfect-square/description/)(<font color="00B8A3">Easy</font>)

限制 :
> 1 <= num <= $2^{31}$ - 1
### Solution
這題有很多解法，用 sqrt 是不好的解法，會有一個測資不會過。所以換個方法，改用數字平方去對，對到剛好一樣救回傳 true。

#### 時間複雜度: $O(lg(n))$

#### 空間複雜度: $O(1)$
```c++=
class Solution {
public:
    bool isPerfectSquare(int num) {
        int fac = 1;
        while(pow(fac,2) < num)
        {
            fac++;
        }
        return !(pow(fac,2) - num);
    }
};
```

## [875.koko eating bananas](https://leetcode.com/problems/koko-eating-bananas/)(<font color="FFC011">Medium</font>) 猴子吃香蕉
## [2300.Successful Pairs of Spells and Potions](https://leetcode.com/problems/successful-pairs-of-spells-and-potions/description/)(<font color="FFC011">Medium</font>)
## [1498. Number of Subsequences That Satisfy the Given Sum Condition](https://leetcode.com/problems/number-of-subsequences-that-satisfy-the-given-sum-condition/description/)(<font color="FFC011">Medium</font>)


