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

// 線形探索
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分探索
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;
}