이진탐색

[lukasjhan]

이진 탐색은 정렬된 배열에서 특정 값을 찾는 효율적인 알고리즘입니다.

1. 전제 조건: 반드시 정렬된 배열에서만 사용 가능합니다.
2. 작동 원리:

• 배열의 중간 지점을 찾아 목표값과 비교합니다
• 중간값이 목표값보다 크면 왼쪽 절반을, 작으면 오른쪽 절반을 탐색합니다
• 이 과정을 목표값을 찾을 때까지 반복합니다

3. 시간 복잡도: O(log n)

• 매 단계마다 탐색 범위가 절반으로 줄어들기 때문에 매우 효율적입니다
• 1,000,000개의 데이터도 최대 20번의 비교로 찾을 수 있습니다

예시 문제

1. 가장 간단한 케이스, 중복이 없는 정렬된 배열에서 특정 값의 위치를 찾는것.

예) [1, 3, 5, 7, 9]에서 5의 인덱스를 찾는 것

예시 코드

function basicBinarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            return mid;
        }
        
        if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return -1; // 값을 찾지 못한 경우
}

2. 중복값이 있는 정렬된 배열에서 중복값중 가장 왼쪽에 있는 위치를 찾는것.

예) [1, 2, 2, 2, 3, 4]에서 가장 왼쪽의 2의 인덱스를 찾는 것

예시 코드

function leftmostBinarySearch(arr: number[], target: number): number {
    let left = 0;
    let right = arr.length - 1;
    let result = -1;
    
    while (left <= right) {
        const mid = Math.floor((left + right) / 2);
        
        if (arr[mid] === target) {
            result = mid; // 현재 위치 저장
            right = mid - 1; // 왼쪽도 계속 탐색
        } else if (arr[mid] < target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return result;
}

3. rotate된 정렬된 배열에서 rotate된 위치를 찾는 것

예) [4, 5, 6, 1, 2, 3]에서 rotate된 위치 1의 인덱스를 찾는것

예시 코드

function findRotationPoint(arr: number[]): number {
    let left = 0;
    let right = arr.length - 1;
    
    // 이미 정렬된 경우
    if (arr[left] < arr[right]) return 0;
    
    while (left < right) {
        const mid = Math.floor((left + right) / 2);
        
        // 중간값이 첫 번째 값보다 크면
        // rotation point는 오른쪽에 있음
        if (arr[mid] > arr[right]) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    
    return left; // rotation point의 인덱스
}