Rustで二分探索法 (0)

以前読んだ『アルゴリズムとデータ構造』を Rust で実装してみたい。本の実装は C++。

GitHub - drken1215/book_algorithm_solution: 拙著「問題解決力を鍛える!アルゴリズムとデータ構造」の補足資料。ソースコードと、章末問題への略解を掲載。

拙著「問題解決力を鍛える!アルゴリズムとデータ構造」の補足資料。ソースコードと、章末問題への略解を掲載。 - GitHub - drken1215/book_algorithm_solution: 拙著「問題解決力を鍛える!アルゴリズムとデータ構造」の補足資料。ソースコードと、章末問題への略解を掲載。

github.com

まずは二分探索を実装してみる。必要なら以下の dependencies を追加。

proconio = "0.4.3"

lib.rs（二分探索の本体）

pub fn binary_search(_n: usize, a: &Vec<i32>, key: i32) -> i32 {
    let mut left = 0 as i32;
    let mut right = (a.len() as i32) - 1;

    while left <= right {
        let mid = left + (right - left) / 2;
        let a_mid = a[mid as usize];
        if a_mid == key {
            println!("Found {} at index {}", key, mid);
            return mid;
        } else if a_mid > key {
            right = mid - 1;
        } else if a_mid < key {
            left = mid + 1;
        }
    }
    println!("Not found {}", key);
    -1
}

main.rs

use proconio::input;
mod lib;

fn input(use_default: bool) -> (usize, Vec<i32>) {
    if use_default {
        let n: usize = 8;
        let a: Vec<i32> = vec![3, 5, 8, 10, 14, 17, 21, 39];
        return (n, a);
    } else {
        println!("Input n and a:");
        input! {
            n: usize,
            a: [i32; n],
        }
        return (n, a);
    }
}

fn main() {
    let use_default = true;
    let (n, a) = input(use_default);
    println!("Your input:");
    println!("n = {}", n);
    println!("a = {:?}", a);
    println!();

    println!("{}", lib::binary_search(n, &a, 10)); // 3
    println!("{}", lib::binary_search(n, &a, 3)); // 0
    println!("{}", lib::binary_search(n, &a, 39)); // 7

    println!("{}", lib::binary_search(n, &a, -100)); // -1
    println!("{}", lib::binary_search(n, &a, 9)); // -1
    println!("{}", lib::binary_search(n, &a, 100)); // -1
}

GitHub のリポジトリはこちら https://github.com/quantized-cube/book_algorithm_solution_rust

参考文献