섹션6. Sort - 8. 이분검색

📌 문제 설명

N개의 자연수가 주어지고, 이 수들을 오름차순 정렬한 뒤 이 중 특정 수 M이 몇 번째에 존재하는지 이분 탐색(Binary Search)으로 찾아야 합니다.

• 중복된 숫자는 존재하지 않음
• 정렬 후 이분 검색을 통해 위치를 찾음

---

📝 입력 & 출력

입력

• 첫 줄에 자연수 N(3≤N≤1,000,000)과 찾고자 하는 수 M이 주어진다.
• 둘째 줄에 N개의 자연수가 공백으로 구분되어 주어진다.

출력

• 오름차순 정렬 후 M이 존재하는 위치(1부터 시작하는 인덱스) 출력

---

🔹 예제 입력 & 출력

예제 입력

8 32
23 87 65 12 57 32 99 81

 

예제 출력

3

---

💡 해결 방법

• 배열을 오름차순으로 정렬한 후 이분 탐색을 수행
• 이분 탐색의 기본 조건:
  • lt는 0부터 시작
  • rt는 배열의 마지막 인덱스
  • mid = (lt + rt) / 2를 기준으로 탐색 범위 축소

---

💻 코드 구현 (Java)

package partSort;

import java.util.Arrays;
import java.util.Scanner;

public class Problem8 {
	public int solution(int n, int m, int[] arr){
		int answer = 0;
		Arrays.sort(arr); // 1. 배열 정렬

		int lt = 0, rt = n - 1;
		while (lt <= rt) {
			int mid = (lt + rt) / 2;
			if (arr[mid] == m) {
				answer = mid + 1; // 인덱스는 1부터 시작
				break;
			}
			if (m > arr[mid]) lt = mid + 1;
			else rt = mid - 1;
		}
		return answer;
	}

	public static void main(String[] args) {
		Problem8 T = new Problem8();
		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.print(T.solution(n, m, arr));
		kb.close();
	}
}

---

📖 코드 설명

1️⃣ 배열 정렬

Arrays.sort(arr);

• 이분 탐색은 정렬된 배열에서만 사용할 수 있기 때문에 먼저 정렬

2️⃣ 이분 탐색 로직

int lt = 0, rt = n - 1;
while (lt <= rt) {
	int mid = (lt + rt) / 2;
	...
}

• mid는 현재 범위의 중간 인덱스
• lt와 rt를 이용해 탐색 범위를 줄여 나감
• arr[mid]와 m을 비교해 범위 조절

---

⏳ 시간 복잡도 분석

정렬	O(N log N)
이분 탐색	O(log N)
전체	O(N log N)

• 정렬 시간이 가장 크므로 전체 시간복잡도는 O(N log N)

---

출처: 인프런 자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비

https://www.inflearn.com/course/자바-알고리즘-문제풀이-코테대비/dashboard

자바(Java) 알고리즘 문제풀이 입문: 코딩테스트 대비 강의 | 김태원 - 인프런