이분탐색은 아이디어는 쉬운데 구현에서 헷갈려서 글을 남겨놓는다.
이분탐색 이란
이분 탐색(Binary Search)은 정렬된 배열이나 리스트에서 특정 값을 효율적으로 찾기 위한 알고리즘이다. 탐색 범위를 절반씩 줄여가며 원하는 값을 찾기 때문에, 시간 복잡도가 O(log n)으로 매우 효율적입니다.
이분 탐색의 원리
이분 탐색은 다음과 같은 절차로 진행된다.
- 탐색 범위 설정: 시작점(left)과 끝점(right)을 지정하여 탐색 범위를 정한다.
- 중간 값 계산: left와 right의 중간 인덱스(mid)를 계산한다.
- 중간 값 비교:
- 중간 값이 찾고자 하는 값(target)과 같으면 탐색을 종료한다.
- 중간 값이 target보다 작으면 left = mid + 1로 탐색 범위를 중간 이후로 좁힌다.
- 중간 값이 target보다 크면 right = mid - 1로 탐색 범위를 중간 이전으로 좁힌다.
- 반복: 위 과정을 left <= right 조건을 만족할 때까지 반복한다. 탐색 범위가 없으면 값이 존재하지 않는 것이므로 종료한다.
이분 탐색의 조건
- 데이터가 정렬되어 있어야 한다: 이분 탐색은 탐색 범위를 절반씩 줄이기 때문에, 데이터가 오름차순 또는 내림차순으로 정렬되어 있어야 한다.
- 인덱스를 통해 중간 값에 접근할 수 있어야 한다: 배열이나 리스트처럼 인덱스를 통해 임의의 위치에 접근 가능한 자료구조에 적용할 수 있다.
이분 탐색의 활용
- 정렬된 배열에서의 값 찾기: 가장 대표적인 사용 예시로, 정렬된 배열에서 특정 값의 존재 여부를 빠르게 판단할 때 사용한다.
- Lower Bound & Upper Bound 찾기:
- Lower Bound: 찾고자 하는 값보다 크거나 같은 첫 번째 위치를 찾는다.
- Upper Bound: 찾고자 하는 값보다 큰 첫 번째 위치를 찾는다.
- 결과가 단조적으로 증가/감소하는 문제 해결: 답이 될 수 있는 범위가 정해져 있고 그 범위 안에서 특정 조건을 만족하는 값을 찾는 경우에도 사용된다.
구현
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
public class BinarySearchExample {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 숫자 N과 S 입력 받기
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int S = Integer.parseInt(st.nextToken());
// N개의 숫자 입력 받기
int[] numbers = new int[N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < N; i++) {
numbers[i] = Integer.parseInt(st.nextToken());
}
// 배열을 정렬한다.
Arrays.sort(numbers);
// 이분 탐색을 통해 타겟 숫자 S의 인덱스 찾기
int resultIndex = binarySearch(numbers, S);
// 결과 출력
System.out.println(resultIndex);
}
// 이분 탐색 메소드
private static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 중간 인덱스 계산
if (arr[mid] == target) {
return mid; // 타겟 숫자를 찾은 경우
} else if (arr[mid] < target) {
left = mid + 1; // 타겟 숫자가 더 크다면 오른쪽으로 이동
} else {
right = mid - 1; // 타겟 숫자가 더 작다면 왼쪽으로 이동
}
}
return -1; // 타겟 숫자를 찾지 못한 경우
}
}