알고리즘, Search, Binary Search

이진 탐색(Binary Search)은 효율적인 검색 알고리즘으로, 정렬된 배열이나 리스트에서 특정 요소를 찾기 위해 사용됩니다. 이진 탐색은 매번 검색 범위를 반으로 줄이기 때문에 시간 복잡도가 O(log n)으로 매우 효율적입니다.

기본 개념

이진 탐색의 기본 개념은 다음과 같습니다:

1. 중간 요소 선택: 검색 범위의 중간 요소를 선택합니다.
2. 비교: 중간 요소와 검색하려는 요소를 비교합니다.
   • 일치하는 경우: 요소를 찾으면 해당 요소의 인덱스를 반환합니다.
   • 작은 경우: 검색하려는 요소가 중간 요소보다 작으면, 검색 범위를 중간 요소의 왼쪽 부분으로 줄입니다.
   • 큰 경우: 검색하려는 요소가 중간 요소보다 크면, 검색 범위를 중간 요소의 오른쪽 부분으로 줄입니다.
3. 반복: 검색 범위가 없을 때까지 1~2번 과정을 반복합니다.
4. 찾지 못한 경우: 검색 범위가 없어지면, 요소가 리스트에 없다는 뜻이므로 -1을 반환합니다.

예제

다음은 자바스크립트로 구현한 이진 탐색의 예제입니다.

function binarySearch(arr, target) {
  var start = 0;
  var end = arr.length - 1;
  var middle = Math.floor((start + end) / 2);
  
  while (arr[middle] !== target && start <= end) {
    if (target < arr[middle]) {
      end = middle - 1;
    } else {
      start = middle + 1;
    }
    middle = Math.floor((start + end) / 2);
  }
  if (arr[middle] === target) {
    return middle;
  }
  return -1;
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearch(arr, 7)); // 6
console.log(binarySearch(arr, 11)); // -1

시간 복잡도

이진 탐색의 시간 복잡도는 다음과 같습니다:

• 최악의 경우 시간 복잡도: O(log n)
• 평균 시간 복잡도: O(log n)
• 최선의 경우 시간 복잡도: O(1)
  • 검색하려는 요소가 중간 요소인 경우입니다.

특징

1. 효율성: 시간 복잡도가 O(log n)으로 매우 효율적입니다.
2. 정렬된 리스트 필요: 이진 탐색은 리스트가 정렬되어 있어야 사용할 수 있습니다.
3. 비교 기반 검색(Comparison Search): 요소들을 비교하여 검색합니다.

장점

1. 빠른 검색 속도: 시간 복잡도가 O(log n)으로, 요소의 수가 많아도 빠르게 검색할 수 있습니다.
2. 제자리 검색(In-place Search): 추가적인 메모리 공간을 사용하지 않습니다.

단점

1. 정렬 필요: 리스트가 정렬되어 있어야만 사용할 수 있습니다.
2. 구현 복잡성: 선형 검색에 비해 구현이 조금 더 복잡할 수 있습니다.

재귀적 구현

이진 탐색은 반복문을 사용하는 방법 외에도 재귀적으로 구현할 수 있습니다. 다음은 재귀적 이진 탐색의 예제입니다.

function binarySearchRecursive(arr, target, left = 0, right = arr.length - 1) {
    if (left > right) {
        return -1; // 요소를 찾지 못하면 -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); // 왼쪽 부분을 검색
    }
}

let arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
console.log(binarySearchRecursive(arr, 7)); // 6
console.log(binarySearchRecursive(arr, 11)); // -1

결론

이진 탐색은 정렬된 리스트에서 매우 효율적으로 요소를 검색할 수 있는 알고리즘입니다. 시간 복잡도가 O(log n)으로, 큰 데이터셋에서도 빠르게 작동합니다. 리스트가 정렬되어 있는 경우에만 사용할 수 있다는 제한이 있지만, 정렬된 데이터를 다루는 경우 이진 탐색은 매우 유용한 도구입니다.