이분검색
문제
설명
임의의 N개의 숫자가 입력으로 주어집니다. N개의 수를 오름차순으로 정렬한 다음 N개의 수 중 한 개의 수인 M이 주어지면
이분검색으로 M이 정렬된 상태에서 몇 번째에 있는지 구하는 프로그램을 작성하세요. 단 중복값은 존재하지 않습니다.
입력
첫 줄에 한 줄에 자연수 N(3<=N<=1,000,000)과 M이 주어집니다.
두 번째 줄에 N개의 수가 공백을 사이에 두고 주어집니다.
출력
첫 줄에 정렬 후 M의 값의 위치 번호를 출력한다.
예시 입력 1
8 32
23 87 65 12 57 32 99 81
예시 출력 1
3
해결방법
- 정렬된 자료 내에서 특정 값을 찾는다.
- 이분 검색(Binary Search) 을 이용하는 방법.
코드
import java.util.*;
class Main {
public int solution(int n, int m, int[] arr) {
int answer = 0;
// 정렬하고 시작
Arrays.sort(arr);
// 이분을 위한 포인터 선언(처음과 끝)
int lt = 0, rt = n - 1;
// 포이넡가 교차할 때 까지 반복한다.
while (lt <= rt) {
// 이분 검색을 위한 중간 위치 설정
int mid = (lt + rt) / 2;
// 가운데 위치의 값이 정답과 일치하면 위치값 리턴
if (arr[mid] == m) {
answer = mid + 1;
break;
}
// 중간 값이 위치 값보다 큰 경우, 오른쪽 포인터 값을 1 감소 시킨다.
// 중간 값이 제시 값보다 큰 경우에는 제시 값이 이전에 있다는 뜻이므로.
if (arr[mid] > m) rt = mid - 1;
// 반대의 경우에는 왼쪽 포인터 값을 1 증가 시킨다.
else lt = mid + 1;
}
return answer;
}
public static void main(String[] args) {
Main.Main T = new Main.Main();
Scanner kb = new Scanner(System.in);
int n = kb.nextInt();
int m = kb.nextInt();
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = kb.nextInt();
System.out.println(T.solution(n, m, arr));
}
}