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

이진 탐색은 정렬된 배열에서 요소를 찾는 고전적인 알고리즘으로, 시간 복잡도가 O(log n)입니다. 각 반복마다 검색 범위를 절반으로 줄이기 때문에 정렬된 데이터셋에서 가장 효율적인 검색 방법 중 하나로 손꼽힙니다.

---

이진 탐색 동작 원리

1. 전제 조건: 데이터셋은 오름차순 또는 내림차순으로 정렬되어 있어야 합니다.
2. 절차:
   • 목표 값을 중간 요소와 비교합니다.
   • 일치하면 검색이 완료됩니다.
   • 목표 값이 더 작으면 왼쪽 절반을 검색합니다.
   • 목표 값이 더 크면 오른쪽 절반을 검색합니다.
3. 목표 값을 찾거나 검색 공간이 비어질 때까지 반복합니다.

---

자바 구현

public class BinarySearch {
    public static int binarySearch(int[] arr, int target) {
        int left = 0, 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; // 목표 값 없음
    }

    public static void main(String[] args) {
        int[] array = {1, 3, 5, 7, 9, 11};
        int target = 5;
        int result = binarySearch(array, target);
        System.out.println("목표 값의 인덱스: " + result);
    }
}

자바 테스트 코드

import static org.junit.Assert.assertEquals;
import org.junit.Test;

public class BinarySearchTest {
    @Test
    public void testBinarySearch() {
        int[] array = {1, 3, 5, 7, 9, 11};
        assertEquals(2, BinarySearch.binarySearch(array, 5));
        assertEquals(-1, BinarySearch.binarySearch(array, 4));
    }
}

---

파이썬 구현

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid  # 목표 값 발견
        elif arr[mid] < target:
            left = mid + 1  # 오른쪽 절반 검색
        else:
            right = mid - 1  # 왼쪽 절반 검색
    return -1  # 목표 값 없음

# 예시 사용
if __name__ == "__main__":
    array = [1, 3, 5, 7, 9, 11]
    target = 5
    result = binary_search(array, target)
    print(f"목표 값의 인덱스: {result}")

파이썬 테스트 코드

import unittest

class TestBinarySearch(unittest.TestCase):
    def test_binary_search(self):
        array = [1, 3, 5, 7, 9, 11]
        self.assertEqual(binary_search(array, 5), 2)
        self.assertEqual(binary_search(array, 4), -1)

if __name__ == "__main__":
    unittest.main()