[Algorithm] 이진 탐색 Binary Search

이진 탐색 시간 복잡도

Binary Search(이진 탐색)은 정렬된 배열에서 값을 효율적으로 찾는 알고리즘입니다. 이진 탐색은 배열을 반복적으로 반을 나누며 검색 범위를 좁히기 때문에 시간 복잡도가 O(logn)입니다.

---

이진 탐색 원리

1. 배열이 오름차순으로 정렬되어 있어야 합니다.
2. 검색 범위의 중간 값을 선택합니다.
3. 중간 값이 찾고자 하는 값과 같으면 검색을 종료합니다.
4. 찾는 값이 중간 값보다 작다면 왼쪽 부분으로 검색 범위를 줄입니다.
5. 반대로 찾는 값이 중간 값보다 크다면 오른쪽 부분으로 검색 범위를 줄입니다.
6. 위 과정을 값을 발견하거나 범위가 없어질 때까지 반복합니다.

---

이진 탐색 구현

자바스크립트로 이진 탐색을 구현하는 방법은 반복문과 재귀 함수 두 가지가 있습니다.

1. 반복문을 사용한 이진 탐색 구현

function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;

    while (left <= right) {
        const mid = Math.floor((left + right) / 2);

        if (arr[mid] === target) {
            return mid; // 값이 발견되면 인덱스를 반환
        } else if (arr[mid] < target) {
            left = mid + 1; // 오른쪽 부분으로 이동
        } else {
            right = mid - 1; // 왼쪽 부분으로 이동
        }
    }

    return -1; // 값을 찾지 못한 경우
}

// 예제
const arr = [1, 3, 5, 7, 9, 11];
console.log(binarySearch(arr, 7)); // 3
console.log(binarySearch(arr, 4)); // -1

2. 재귀 함수를 사용한 이진 탐색 구현

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) {
        return -1; // 값을 찾지 못한 경우
    }

    const mid = Math.floor((left + right) / 2);

    if (arr[mid] === target) {
        return mid; // 값이 발견되면 인덱스를 반환
    } else if (arr[mid] < target) {
        return binarySearchRecursive(arr, target, mid + 1, right); // 오른쪽 부분
    } else {
        return binarySearchRecursive(arr, target, left, mid - 1); // 왼쪽 부분
    }
}

// 예제
const arr = [1, 3, 5, 7, 9, 11];
console.log(binarySearchRecursive(arr, 7)); // 3
console.log(binarySearchRecursive(arr, 4)); // -1

---

이진 탐색의 장점과 단점

장점

검색 속도가 빠릅니다. - O(logN)

배열이 정렬되어 있다면 효율적으로 사용 가능합니다.

단점

배열이 정렬되어 있어야만 작동합니다.

배열의 크기가 작다면 선형 탐색(Linear Search)이 더 효율적일 수 있습니다.