二分探索

検索範囲のど真ん中のデータを見て大小比較をし、検索範囲を半分ずつ狭めていく

実装

標準ライブラリによる提供はないため、自分で実装しよう

以下は、単純な数値を用いた二分探索を行う

もちろん、比較用の関数だったり、比較演算子が使える対象であればなんでも探索可能

同じ値がない場合、引数の値より大きな最小の値のindexを返す

code:js

function binarySearch(array, element) {

let start = 0;

let end = array.length;

while (start < end) {

const center = (start + end) >> 1;

if (centerElement < element) {

start = center + 1;

} else {

end = center;

}

}

return start;

}

スライス内に複数一致する値がある場合、その中のどれかが返ってくる

code:rust

fn main() {

let r = s.binary_search(&1);

println!("{:?}", r); // Ok(4)

}

code:rust

fn main() {

let i = s.partition_point(|&x| x < 1);

println!("{:?}", i); // 2

}