[백준] 온라인 저지 11663번 : 선분 위의 점(Java), 이분 탐색

이분 탐색 풀이

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

public class Main {
    
    static int[] spot;
	static int N;
    
    public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		N = Integer.parseInt(st.nextToken()); // 점 개수
		int M = Integer.parseInt(st.nextToken()); // 선분 개수

		// 점 배열
		spot = new int[N];
		st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			spot[i] = Integer.parseInt(st.nextToken());
		}

		Arrays.sort(spot);

		// 선분
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken()); // 시작점
			int e = Integer.parseInt(st.nextToken()); // 끝점

			int lowIdx = findLowIdx(s);
			int highIdx = findHighIdx(e);

			System.out.println(highIdx - lowIdx);
		}
	}
    
    private static int findLowIdx(int target) {
		int mid = 0;
		int left = 0;
		int right = N;

		while(left < right) {
			mid = (left+right) / 2;

			if(spot[mid] >= target) {
				right = mid;
			} else {
				left = mid + 1;
			}
		}
		return left;
	}

	private static int findHighIdx(int target) {
		int mid = 0;
		int left = 0;
		int right = N;

		while(left < right) {
			mid = (left+right) / 2;

			if(spot[mid] <= target) {
				left = mid + 1;
			} else {
				right = mid;
			}
		}
		return left;
	}
}