자바 코딩테스트 강좌, 이진 탐색

작성자: 조광형

작성일: 2024년 11월 26일

1. 이진 탐색 알고리즘 소개

이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾기 위해 사용하는 알고리즘입니다. 배열의 중간값을 비교하여 원하는 값이 중간값보다 작으면 왼쪽 부분에서, 크면 오른쪽 부분에서 값을 찾는 방식으로 구현됩니다. 이진 탐색은 시간 복잡도가 O(log n)으로 매우 효율적입니다.

이진 탐색을 사용하기 위해서는 배열이 반드시 정렬되어 있어야 하며, 그렇지 않을 경우 다른 탐색 방법인 선형 탐색(Linear Search)을 사용해야 합니다.

2. 이진 탐색 문제 예제

문제: 특정 값의 인덱스 찾기

정렬된 정수 배열 nums와 정수 target가 주어질 때, target의 인덱스를 찾아 반환하는 함수 binarySearch를 작성하시오. target이 존재하지 않으면 -1을 반환해야 합니다.

예제 입력

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9]
target = 5

예제 출력

4

3. 문제 풀이 과정

3.1 문제 분석

이 문제는 주어진 nums 배열에서 target의 인덱스를 찾는 것이므로, 우선 배열이 정렬되어 있음을 활용하는 것이 중요합니다. 중간값을 계산하여 target과의 비교를 통해 탐색 범위를 좁혀가는 방식으로 탐색을 수행할 것입니다.

3.2 알고리즘 설계

이진 탐색 알고리즘은 다음과 같은 단계를 포함합니다:

  1. 배열의 시작 인덱스 left와 끝 인덱스 right를 초기화합니다.
  2. 중간 인덱스 mid를 계산합니다: mid = (left + right) / 2.
  3. 중간값 nums[mid]와 target을 비교합니다.
  4. 중간값이 target과 같으면 mid를 반환합니다.
  5. 중간값이 target보다 작으면 left = mid + 1로 업데이트하고, 그렇지 않으면 right = mid - 1로 업데이트합니다.
  6. 이 과정을 left가 right보다 작거나 같을 때까지 반복합니다.
  7. 감소한 경우 target가 배열에 없음을 나타내며 -1를 반환합니다.

3.3 자바 코드 구현

위의 알고리즘을 자바로 구현해 보겠습니다.


public class BinarySearch {
    public static int binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

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

            if (nums[mid] == target) {
                return mid; // 존재 시 인덱스 반환
            } else if (nums[mid] < target) {
                left = mid + 1; // 오른편 탐색
            } else {
                right = mid - 1; // 왼편 탐색
            }
        }

        return -1; // 존재하지 않으면 -1 반환
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3, 4, 5, 6, 7, 8, 9};
        int target = 5;
        int result = binarySearch(nums, target);
        System.out.println(result);
    }
}

4. 시간 복잡도 분석

이진 탐색 알고리즘의 시간 복잡도는 O(log n)입니다. 이는 매번 탐색할 때마다 배열의 크기가 절반으로 줄어들기 때문입니다. 따라서 이진 탐색은 데이터 양이 많을수록 더욱 유리한 성능을 보입니다.

5. 결론

이번 강좌에서는 이진 탐색의 개념과 이를 활용한 문제를 살펴보았습니다. 이진 탐색은 정렬된 배열에 대한 효율적인 탐색 방법으로, 다양한 코딩 테스트에서 자주 출제되는 기본적인 알고리즘입니다. 실제 코딩 테스트에 대비해 다양한 이진 탐색 문제를 풀어보며 실력을 점검하시기 바랍니다.

감사합니다!