이진 검색 (Binary Search)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def binary_search(arr, target):
    """
    정렬된 배열에서 대상 값의 인덱스를 찾는 이진 탐색 함수
    
    Args:
        arr: 정렬된 배열
        target: 찾으려는 값
        
    Returns:
        대상 값의 인덱스 또는 찾지 못한 경우 -1
    """
    left = 0
    right = len(arr) - 1
    
    while left <= right:
        # 중간 인덱스 계산 (오버플로우 방지를 위한 최적화 방법)
        mid = left + (right - left) // 2
        
        # 중간 요소가 대상 값인 경우
        if arr[mid] == target:
            return mid
        
        # 대상 값이 중간 요소보다 작은 경우, 왼쪽 부분 배열 검색
        elif arr[mid] > target:
            right = mid - 1
            
        # 대상 값이 중간 요소보다 큰 경우, 오른쪽 부분 배열 검색
        else:
            left = mid + 1
            
    # 값을 찾지 못한 경우
    return -1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

/**
 * 정렬된 배열에서 대상 값의 인덱스를 찾는 이진 탐색 함수
 * @param {Array} arr - 정렬된 배열
 * @param {number} target - 찾으려는 값
 * @returns {number} - 대상 값의 인덱스 또는 찾지 못한 경우 -1
 */
function binarySearch(arr, target) {
    let left = 0;
    let right = arr.length - 1;
    
    while (left <= right) {
        // 중간 인덱스 계산 (오버플로우 방지를 위한 방법)
        const mid = Math.floor(left + (right - left) / 2);
        
        // 중간 요소가 대상 값인 경우
        if (arr[mid] === target) {
            return mid;
        }
        
        // 대상 값이 중간 요소보다 작은 경우, 왼쪽 부분 배열 검색
        else if (arr[mid] > target) {
            right = mid - 1;
        }
        
        // 대상 값이 중간 요소보다 큰 경우, 오른쪽 부분 배열 검색
        else {
            left = mid + 1;
        }
    }
    
    // 값을 찾지 못한 경우
    return -1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

def binary_search_recursive(arr, target, left, right):
    """
    재귀적 이진 탐색 구현
    
    Args:
        arr: 정렬된 배열
        target: 찾으려는 값
        left: 왼쪽 경계 인덱스
        right: 오른쪽 경계 인덱스
        
    Returns:
        대상 값의 인덱스 또는 찾지 못한 경우 -1
    """
    # 기저 사례: 검색 범위가 없는 경우
    if left > right:
        return -1
    
    # 중간 인덱스 계산
    mid = left + (right - left) // 2
    
    # 중간 요소가 대상 값인 경우
    if arr[mid] == target:
        return mid
    
    # 대상 값이 중간 요소보다 작은 경우, 왼쪽 부분 배열 검색
    elif arr[mid] > target:
        return binary_search_recursive(arr, target, left, mid - 1)
    
    # 대상 값이 중간 요소보다 큰 경우, 오른쪽 부분 배열 검색
    else:
        return binary_search_recursive(arr, target, mid + 1, right)

# 사용 예:
# result = binary_search_recursive(sorted_array, target_value, 0, len(sorted_array) - 1)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

def lower_bound(arr, target):
    """배열에서 target 이상인 첫 번째 요소의 인덱스를 찾습니다."""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
            
    return left

def upper_bound(arr, target):
    """배열에서 target보다 큰 첫 번째 요소의 인덱스를 찾습니다."""
    left, right = 0, len(arr)
    
    while left < right:
        mid = left + (right - left) // 2
        if arr[mid] <= target:
            left = mid + 1
        else:
            right = mid
            
    return left

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def search_in_rotated_array(arr, target):
    """회전된 정렬 배열에서 대상 값을 찾습니다."""
    left, right = 0, len(arr) - 1
    
    while left <= right:
        mid = left + (right - left) // 2
        
        if arr[mid] == target:
            return mid
            
        # 왼쪽 절반이 정렬되어 있는 경우
        if arr[left] <= arr[mid]:
            if arr[left] <= target < arr[mid]:
                right = mid - 1
            else:
                left = mid + 1
        # 오른쪽 절반이 정렬되어 있는 경우
        else:
            if arr[mid] < target <= arr[right]:
                left = mid + 1
            else:
                right = mid - 1
                
    return -1