분할 정복: 이진 탐색

Shawn Kang·2023년 4월 2일

Rust python 알고리즘

알고리즘

목록 보기

1/5

접근

분할 정복의 접근 방식은 아래와 같다:

하나의 문제를 하나 이상의 그보다 작은 크기의 문제로 분할한다.
분할된 각각의 작은 문제를 해결한다.
(필요할 경우) 각각의 작은 문제에서 도출된 답을 합친다.

이를 이진 탐색에 적용해보면:

입력된 배열을 2개로 분할한다.
분할된 배열에서 탐색을 진행하고, 탐색에 실패하면 다시 배열을 2개로 분할한다.

이진 탐색에서는 분할된 2개의 배열 중 1개의 배열만 취하므로, 해답 도출을 위해 답을 합치는 절차는 생략해도 된다.

Rust 코드

반복 (Iteration)

fn bs_iteration(arr: &[i32], target: &i32) -> Option<usize> {
	let length = arr.len();
    
    let mut mid = length / 2;
    let mut low = 0;
    let mut high = length - 1;
   	let mut current = arr[mid];
    
    while low <= high { match current.cmp(&target) {
    		// target과 current가 같을 경우
    		std::cmp::Ordering::Equal => return Some(mid),
            
            // current가 target 좌측에 있을 경우 (low < current < target < high)
            std::cmp::Ordering::Less => low = mid + 1,
            
            // current가 target 우측에 있을 경우 (low < target < current < high)
            std::cmp::Ordering::Greater => high = mid - 1, 
    	}
        
        mid = (low + high) / 2;
        current = arr[mid];
    }
    
    // 탐색에 실패한 경우
    return None;
}

주목할 만한 코드

let mut high = length - 1;

배열의 인덱스는 0부터 시작하지만 length는 길이를 그대로 반환하기 때문에, high에서 1을 빼 주었다.

match current.cmp(&target) {
    std::cmp::Ordering::Equal => return Some(mid),
    std::cmp::Ordering::Less => low = mid + 1,
    std::cmp::Ordering::Greater => high = mid - 1,
}

cmp() 함수는 기준이 함수를 부르는 변수인 것으로 보인다. 이 코드에서 Less의 의미는 함수를 부른 current가 &target에 비해 작은 경우를 의미하는 듯함.
이게 Rusty한 접근이라고 어디서 봤다. 이유는 잘 모르겠음.

fn binary_search() -> Option<usize> {
	// ...
    return None;
}

Rust 공식 문서는 Option에 대해 아래와 같이 설명하고 있다:

Type Option represents an optional value: every Option is either Some and contains a value, or None, and does not. Option types are very common in Rust code, as they have a number of uses:
(생략)...
- Return value for otherwise reporting simple errors, where None is returned on error

재귀 (Recursion)

fn bs_recursion(arr: &[i32], target: i32, low: usize, high: usize) -> Option<usize> {
    let mid = (low + high) / 2;
    let current = arr[mid];

    if low > high {
        return None;
    } else {
        match current.cmp(&target) {
            std::cmp::Ordering::Equal => return Some(mid),
            std::cmp::Ordering::Less => bn_recursion(&arr, target, mid + 1, high), 
            std::cmp::Ordering::Greater => bn_recursion(&arr, target, low, mid - 1)
        }
    }
}

주목할 만한 코드

주목할 만한 코드라기보다는... std::cmp::Ordering에서 제공하는 항목이 Less, Greater, Equal 이렇게 셋 뿐이다. 이상이나 이하에 대한 표현이 없다는 말. 원래는 조건문을 쓰지 않고 low.cmp(&high)로 'Rusty'하게 코드를 짜 보려고 했는데, Ordering으로는 이상과 이하를 표현할 수 없다는 걸 알고 다시 조건문으로 돌아왔다.

Python 코드

반복 (Iteration)

def binary_search_iteration(arr: list, target: int) -> int:
    low = 0
    high = len(arr)
    mid = (low + high) // 2

    if (low > high): return -1
    else:
        while (True):
            if (target == arr[mid]): return mid
            elif (target < arr[mid]): high = mid - 1
            else: low = mid + 1
            mid = (low + high) // 2

재귀 (Recursion)

def binary_search_recursion(arr: list, target: int, low: int, high: int) -> int:
    mid = (low + high) // 2

    if (low > high): return -1
    else:
        if (target == arr[mid]): return mid
        elif (target < arr[mid]): return binary_search_recursion(arr, target, low, mid - 1)
        else: return binary_search_recursion(arr, target, mid + 1, high)