이진 탐색 - 1. 정렬된 배열에서 특정 수의 개수 구하기

문제

N개의 원소를 포함하고 있는 수열이 오름차순으로 정렬되어 있습니다. 이때 이 수열에서 x가 등장하는 횟수를 계산하세요. 예를 들어 수열 {1, 1, 2, 2, 2, 2, 3}이 있을 때 x = 2라면, 현재 수열에서 값이 2인 원소가 4개이므로 4를 출력합니다.

단, 이 문제는 시간 복잡도 O(log N)으로 알고리즘을 설계하지 않으면 '시간 초과' 판정을 받습니다.

입력 조건
첫째 줄에 N과 x가 정수 형태로 공백으로 구분되어 입력됩니다.
(1 ≤ N ≤ 1,000,000), (-10⁹ ≤ x ≤ 10⁹)

둘째 줄에 N개의 원소가 정수 형태로 공백으로 구분되어 입력됩니다.
(-10⁹ ≤ 각 원소의 값 ≤ 10⁹)

출력 조건
수열의 원소 중에서 값이 x인 원소의 개수를 출력합니다. 단, 값이 x인 원소가 하나도 없다면 -1을 출력합니다.

입력
7 2
1 1 2 2 2 2 3

출력
4

입력
7 4
1 1 2 2 2 2 3

출력
-1

구현코드

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

public class Main {

	public static int cnt;
	public static void main(String[] args)throws IOException {
		// TODO Auto-generated method stub
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int target = Integer.parseInt(st.nextToken());
		int[] arr = new int[n];
		st = new StringTokenizer(br.readLine());
		for(int i = 0 ; i < n ; i++) {
			arr[i] =  Integer.parseInt(st.nextToken());
		}
		cnt = 0;
		binarySearch(0, n-1, target, arr);
		if(cnt == 0) {
			System.out.println(-1);
		}else {
			System.out.println(cnt);
		}
		
	}
	
	public static void binarySearch(int start, int end ,int target, int[] arr) {
		if(start > end) {
			return;
		}
		int mid = (start + end) / 2;
		
		if(arr[mid] == target) {
			cnt++;
			binarySearch(start, mid-1, target, arr );
			binarySearch(mid+1, end, target, arr);
		}
		else if(arr[mid] > target) {
			binarySearch(start, mid-1, target, arr );
		}else {
			binarySearch(mid+1, end, target, arr);
		}
	}

}

코드해석

이진탐색을 이용하여 값을 찾는문제이다. 보통의 이진탐색 문제들은 값 한개를 찾는 문제이라면
이 문제는 target 이 몇개있는지를 구하는 문제이다. 그래서 cnt 를 전역변수로 지정한 후, binarySearch메서드를 구현하였는데 타입인 void 이다. start 가 end 보다 크다면 return 해주고, mid 값은 시작, 끝 을더한 후 2로 나눈 값 그리고

if(arr[mid] == target) {
			cnt++;
			binarySearch(start, mid-1, target, arr );
			binarySearch(mid+1, end, target, arr);
		}
		else if(arr[mid] > target) {
			binarySearch(start, mid-1, target, arr );
		}else {
			binarySearch(mid+1, end, target, arr);
		} 

이 코드를 보면 원래 정석의 binarySearch에선 mid 값을 return 해주지만 값을 찾았을 때 양옆에 값들이 같은 값이 있을 수있기 때문에 양쪽으로 진행시켜준다. 그리고 값을 찾을시 cnt ++ 해주면 쉽게 풀수있는문제이다.