⚙️

Rustで線形探索と2分探索を書いてみる

2022/04/10に公開

アルゴリズムの練習がてら書いてみた。
ハッシュ探索はどうやって書けばいいのか分からなかったのでひとまずパス。

線形探索

// 線形探索
fn linear_search(vec: &Vec<i32>, n: i32) -> Option<usize> {

    // i:探索している要素の位置(初期値:0)
    // len:配列の長さ
    let mut i = 0;
    let len = vec.len();

    // iが配列の長さを超えるまで探索する
    while i < len {
        if vec[i] == n {
            return Some(i);
        }
        i += 1;
    }
    
    // 見つからなければNoneを返す
    return None;
}

2分探索

// 2分探索
fn binary_search(vec: &Vec<i32>, n: i32) -> Option<usize> {
    // len:配列の長さ
    let len = vec.len();

    // is_ascending:昇順ならtrue, 降順ならfalse
    let is_ascending = if vec[0] <= vec[len - 1] { true } else { false };

    // low:探索範囲の下限値(初期値:0)
    // high:探索範囲の上限値(初期値:配列の長さ-1)
    let mut low = 0;
    let mut high = len - 1;

    // 探索範囲の下限値が上限値を超えるまで探索する
    while low <= high {
        // mid:探索する要素の位置
        let mid = (low + high) / 2;
       
        match vec[mid] {
	    // 探索している要素が見つかったらSome(mid)を返す
            x if x == n => return Some(mid),
	    
	    // 見つからなかったらis_ascendingによってlowかhighを更新する
            x if x < n => {
                low = if is_ascending { mid + 1 } else { low };
                high = if is_ascending { high } else { mid - 1 };
            }
            x if x > n => {
                low = if is_ascending { low } else { mid + 1 };
                high = if is_ascending { mid - 1 } else { high };
            }
            _ => {}
        }
    }

    // 見つからなければNoneを返す
    return None;
}

Discussion