제곱근 구하기 (이진탐색)

제곱근 구하기 (이진탐색)

21억의 제곱근은 얼마일까?

약 45000 인 것 같은데, 한번 구해볼까?

✅ 코드

package ps;

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;


public class Solution {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int n = 2100000000;
		int left = 1;
		int right = n;
		int res = 0;
		
		while (left <= right) {
			int mid = (left + right) / 2;
			
			// 오버플로우 방지라서 mid * mid > n 아님
			if (mid > n/mid) {
				right = mid - 1;
			}
			else if (mid <= n/mid) {
				res = mid;
				left = mid + 1;
			}
		}
		System.out.println(res);
		
		
	}
}

출력값 : 45825