이분탐색, 2포인터

GoRuth·2025년 6월 9일

이분 탐색

개념

정렬된 배열에서 특정 값을 찾거나 조건을 만족하는 값을 찾는 데 사용.
배열을 절반씩 나눠가며 탐색 -> O(log N)의 시간 복잡도.

적용 조건

데이터가 오름차순 또는 내림차순으로 정렬되어 있어야 함
값 존재 여부 판단 문제, 최솟값/최댓값을 찾는 결정 문제에 적합

기본 구현 (Java 기준)

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

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

            if (arr[mid] == target) return mid;
            else if (arr[mid] < target) left = mid + 1;
            else right = mid - 1;
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {1, 3, 5, 7, 9, 11};
        int target = 7;
        System.out.println(binarySearch(arr, target));
    }
}

대표 문제 유형

특정 수가 배열에 존재하는가?
최소/최대 조건을 만족하는 값 찾기
Lower Bound / Upper Bound 위치 찾기

투 포인터

개념

두 개의 포인터를 배열의 양 끝 또는 특정 위치에 두고, 서로를 좁히거나 밀어가며 조건을 만족하는 구간을 탐색.
일반적으로 O(N)의 시간 복잡도.

적용 조건

데이터가 정렬되어 있거나, 정렬할 수 있는 경우
부분합, 쌍 찾기, 구간 문제에 적합

기본 구현

public class TwoPointerExample {
    public static boolean hasTwoSum(int[] arr, int target) {
        Arrays.sort(arr);
        int left = 0, right = arr.length - 1;

        while (left < right) {
            int sum = arr[left] + arr[right];

            if (sum == target) return true;
            else if (sum < target) left++;
            else right--;
        }

        return false;
    }

    public static void main(String[] args) {
        int[] arr = {1, 4, 2, 7, 11};
        int target = 9;
        System.out.println(hasTwoSum(arr, target));
    }
}