[알고리즘] 이진 탐색(Binary Search)

이진 탐색(Binary Search)이란?

• 정의: 이진 탐색은 정렬된 배열에서 값을 찾는 알고리즘으로, 검색 범위를 절반씩 좁혀가며 값을 탐색한다.
• 특징
  - 배열 또는 리스트가 정렬되어 있어야 한다.
  - 탐색 범위를 매번 절반으로 줄이므로 매우 빠르다.
• 장단점
  - 장점
     - 정렬된 데이터에서 매우 빠름
     - O(log n)의 시간 복잡도로 대용량 데이터 처리 가능
  - 단점
     - 데이터가 반드시 정렬되어 있어야 함
     - 재귀 방식에서는 스택 오버플로우 위험

---

이진 탐색의 동작 원리

1. 시작점(Start)과 끝점(End)을 설정한다.

 

2. 중간점(Mid)을 계산한다: Mid = (Start + End) / 2

 

3. 중간점의 값과 목표값(Target)을 비교한다.

• 중간점 값  == 목표값 -> 검색 성공
• 중간점 값 < 목표값 -> 검색 범위를 오른쪽 절반으로 좁힘
• 중간점 값 > 목표값 -> 검색 범위를 왼쪽 절반으로 좁힙

 

4. 위 과정을 목표값을 찾거나 검색 범위가 없을 때까지 반복한다.

---

이진 탐색의 구현 방법

1. 반복문(Iterative) 방식

public int binarySearch(int[] arr, int target) {
    int start = 0;
    int end = arr.length - 1;

    while (start <= end) {
        int mid = start + (end - start) / 2; // 중간점 계산
        if (arr[mid] == target) {
            return mid; // 목표값 찾음
        } else if (arr[mid] < target) {
            start = mid + 1; // 오른쪽 탐색
        } else {
            end = mid - 1; // 왼쪽 탐색
        }
    }
    return -1; // 목표값이 없음
}

 

 

2. 재귀(Recursive) 방식

public int binarySearchRecursive(int[] arr, int target, int start, int end) {
    if (start > end) {
        return -1; // 목표값 없음
    }
    int mid = start + (end - start) / 2;
    if (arr[mid] == target) {
        return mid; // 목표값 찾음
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, end); // 오른쪽 탐색
    } else {
        return binarySearchRecursive(arr, target, start, mid - 1); // 왼쪽 탐색
    }
}

 

---

시간 복잡도와 공간 복잡도

• 시간 복잡도
  - O(log n): 매번 탐색 범위를 절반으로 줄이기 때문
• 공간 복잡도
  - 반복문 방식: O(1) (추가 공간 필요 없음)
  - 재귀 방식: O(log n) (재귀 호출 스택 사용)

---

이진 탐색의 활용 예시

1. 배열에서 특정 값 찾기

• 정렬된 배열에서 빠르게 값을 찾음

2. Lower Bound와 Upper Bound

• Lower Bound: 특정 값 이상인 첫 번째 위치 찾기
• Upper Bound: 특정 값보다 큰 첫 번쨰 위치 찾기

3. 코딩 테스트 활용 사례

• 두 배열의 합: 특정 합을 이루는 쌍 찾기
• K번째 원소 찾기: 정렬된 배열에서 K번쨰 값을 찾음
• 최적화 문제: 범위를 좁히며 최적의 값을 찾음

---

Lower Bound와 Upper Bound 구현 예제

1. Lower Bound 구현

public int lowerBound(int[] arr, int target) {
    int start = 0, end = arr.length;
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] >= target) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    return start;
}

 

 

2. Upper Bound 구현

public int upperBound(int[] arr, int target) {
    int start = 0, end = arr.length;
    while (start < end) {
        int mid = start + (end - start) / 2;
        if (arr[mid] > target) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    return start;
}

 

---

이진 탐색과 선형 탐색의 비교

구분	이진 탐색(Binary Search)	선형 탐색(Linear Search)
시간 복잡도	O(log n)	O(n)
데이터 정렬 필요성	정렬 필요	정렬 불필요
속도	매우 빠름	느림