[JS] 탐색 알고리즘 (이진 탐색) / 반복문, 재귀함수 함수비교

🚀 문제

정렬된 배열에서 특정 값을 찾는 이진 탐색 알고리즘을 구현하시오.

function binarySearch(arr, target) {
  // 여기에 코드 작성
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 5)); // 2

---

🔹 코드

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

    while (left <= right) {
        let 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; // 타겟 값이 배열에 없으면 -1을 반환
}


console.log(binarySearch([1, 3, 5, 7, 9, 11], 5)); // 2

---

📌 이진 탐색 문제

🔎 1️⃣ 문제가 묻는 것

이진 탐색 문제에서 요구하는 것은 정렬된 배열에서 특정 값을 효율적으로 찾는 방법입니다. 이진 탐색은 배열을 반씩 나누어가며 탐색을 진행하므로 시간 복잡도를 O(log N)로 줄일 수 있습니다. 문제는 일반적으로 배열이 정렬되어 있을 때 주어지며, 목표는 주어진 값이 배열에 있는지 여부를 확인하는 것입니다.

이진 탐색이란?

이진 탐색(Binary Search)은 정렬된 배열에서 특정 값을 찾을 때 반복적으로 배열을 절반씩 나누며 탐색하는 알고리즘입니다. 배열의 크기가 n일 경우, 이진 탐색의 시간 복잡도는 O(log n)입니다. 이는 배열 크기가 커지더라도 탐색 시간이 상대적으로 짧다는 장점이 있습니다.

이진 탐색의 원리

1. 배열의 중간값을 찾습니다.
2. 중간값과 찾고자 하는 값(target)을 비교합니다.
3. 만약 중간값이 찾고자 하는 값보다 크면, 배열의 왼쪽 절반을 탐색합니다.
4. 만약 중간값이 찾고자 하는 값보다 작으면, 배열의 오른쪽 절반을 탐색합니다.
5. 찾고자 하는 값을 찾을 때까지 이를 반복하며, 찾지 못한 경우 -1을 반환합니다.

🔎 2️⃣ 구현 방식

이진 탐색은 재귀적 방법이나 반복문 방식으로 구현할 수 있습니다.

✅ (1) 재귀 

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) return -1;

    let 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); // 왼쪽 절반 탐색
    }
}

console.log(binarySearchRecursive([1, 3, 5, 7, 9, 11], 5)); // 2

• 시간 복잡도: O(log n) 
• 공간 복잡도: O(log n) → 재귀 호출로 인해 스택 프레임이 n개 쌓임
• 단점: 스택 오버플로우 위험, 공간 복잡도가 O(log n)으로 상대적으로 더 많은 메모리를 소비합니다.

✅ (2) 반복문

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

    while (left <= right) {
        let 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; // 타겟 값이 배열에 없으면 -1을 반환
}

console.log(binarySearch([1, 3, 5, 7, 9, 11], 5)); // 2

• 시간 복잡도: O(log n) 
• 공간 복잡도: O(1)
• 단점: 코드가 상대적으로 길어질 수 있음

 

🔑 결론

• 이진 탐색은 효율적인 탐색 알고리즘으로, 정렬된 배열에서 특정 값을 찾을 때 매우 유용
• 반복문을 이용한 방식이 직관적이고 성능 면에서 유리
• 재귀 방식은 코드가 간결해지지만 스택 오버플로우를 유발할 수 있기 때문에 배열의 크기가 매우 큰 경우 반복문 방식이 더 나음