二分：查找完全平方数个数

import java.io.IOException;
import java.util.*;

public class Main {
    static int num[] = new int[31623];

    static boolean check(int mid,int x){
        if(num[mid] <= x) return true;
        return false;
    }
    static int f(int x){
        if(x < 0)return 0;
        int l = 0,r = 31622,mid = 0,ans = 0;
        while(r >= l){
            mid = (l + r) / 2;
            if(check(mid,x)){
                l = mid + 1;
                ans = l;
            }else
                r = mid - 1;

        }
        return ans;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        for (int i = 1; i <= 31622; i++) {
            num[i] = i * i;
        }
        int n = sc.nextInt();
        while(n-- > 0){
            int l = sc.nextInt();
            int r = sc.nextInt();
            int ans = f(r) - f(l - 1);
            System.out.println(ans);

        }


    }

}

##其实不用二分的话，更简单，只是为了更加熟悉二分而学习二分。题目的意思就是在范围里面找完全平方数的个数，那就直接sqrt（r）-sqrt（l）+1就可以得到结果了。 ##其实在二分的思路也是一样的，要写一个方法，啥方法？就是二分查找从0到这一个数范围内的完全平方数，那么写这一个方法之前，还要写一个check，num数组是吧1e9之内的完全平方数都装进来了，那么直接用x和num[mid]对比，如果是相同或者是x比较大那就继续向右查找，直到最后正确结果。