이분 탐색

이분 탐색이란

이분탐색(Binary Search)은 정렬된 배열에서 원하는 값을 빠르게 찾기 위한 알고리즘입니다.

시간 복잡도가 O(log⁡n)이기 때문에, 탐색 속도가 매우 빠르고 효율적입니다.

이분탐색의 핵심 개념은 탐색 범위를 반씩 줄여가며 원하는 값을 찾아가는 데 있습니다.

이분 탐색의 작동 원리

1. 초기 설정: 탐색 범위의 시작점 left와 끝점 right를 설정합니다. 처음에는 left는 배열의 첫 번째 인덱스, right는 마지막 인덱스로 설정합니다.
2. 중간값 계산: left와 right의 중간 인덱스 mid를 계산합니다. mid = (left + right) // 2.
3. 값 비교:
   • 중간값 arr[mid]가 찾고자 하는 값 target과 일치하면, mid를 반환하여 탐색을 종료합니다.
   • arr[mid]가 target보다 작으면, target은 중간값 오른쪽에 있을 가능성이 있으므로 left = mid + 1로 설정하여 탐색 범위를 오른쪽 절반으로 좁힙니다.
   • arr[mid]가 target보다 크면, target은 중간값 왼쪽에 있을 가능성이 있으므로 right = mid - 1로 설정하여 탐색 범위를 왼쪽 절반으로 좁힙니다.
4. 반복: 위 과정을 left가 right보다 작거나 같을 때까지 반복합니다. 탐색 범위가 더 이상 없을 경우 target은 배열에 없는 것으로 간주하고 실패를 반환합니다.

예시 코드

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; // 찾지 못하면 -1 반환
}

// 예제 사용
const sortedArray = [1, 3, 5, 7, 9, 11];
const target = 7;
const result = binarySearch(sortedArray, target);

console.log(result); // 인덱스 3을 출력 (타겟 값이 위치한 인덱스)

 

while문 안의 로직은 요구사항에 맞게 변경해서 원하는 target 값을 찾아내도록 수정할 수 있습니다.

주의할 점

 

• 시간 복잡도가 O(log⁡n)으로 리스트 또는 데이터가 큰 경우 빠르게 탐색가능하지만, 데이터가 순차적 혹은 정렬된 상태여야 합니다.