Rust 연습 문제

Binary Search in Rust

Find a value in a sorted slice by halving the search range at every step.

초급
3분 분량
실행 가능한 예제 1개

배울 내용

low, high and middle
Returning Option<usize>
Why it is fast

코드 실행 →

Search for 23

164

235

386

567

Found at index 5 after three steps.

Halve the range each step

Binary search looks at the middle of a sorted list and throws away the half that cannot contain the target. Each step halves the work, so it is very fast on large lists.

low and high mark the part that is still being searched. The function returns Some(index) when the target is found and None when the range becomes empty. low + (high - low) / 2 finds the middle without overflow.

핵심 포인트

The list must be sorted.
Each step throws away half.
None means the value is not there.

실행 가능한 Rust 예제

Rust

코드 실행 →

main.rs

fn binary_search(items: &[i32], target: i32) -> Option<usize> {
    let mut low = 0;
    let mut high = items.len();
    while low < high {
        let middle = low + (high - low) / 2;
        if items[middle] == target {
            return Some(middle);
        } else if items[middle] < target {
            low = middle + 1;
        } else {
            high = middle;
        }
    }
    None
}

fn main() {
    let sorted = [2, 5, 8, 12, 16, 23, 38, 56];
    println!("{:?}", binary_search(&sorted, 23));
    println!("{:?}", binary_search(&sorted, 7));
}

이 예제의 실행 버튼 만들기 코드 실행 결과

Some(5)
None

연습

예제를 온라인 컴파일러에서 열고 값을 바꾸거나 한 줄을 추가한 다음, 실행하기 전에 출력을 예상해 보세요. 그런 다음 일부러 코드를 망가뜨리고 컴파일러 메시지를 읽어 보세요.

이 레슨을 마쳤나요?

학습 완료로 표시하면 진행 상황을 기록할 수 있습니다.

다음: Structs →

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

모든 챌린지