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 のレビューも受けられます。

すべてのチャレンジ