A11 - Binary Search 1¶

• created: 2022-12-28 wed
• ご意見・ご要望はissue・プルリク用のGitHubまで
• 競技プログラミングのためのF#入門
• GitHub上の対応ディレクトリ
• 公式ページ
• 要点: アルゴリズム

入出力¶

1
2
3

let N,X = stdin.ReadLine().Split() |> Array.map int |> (fun x -> x.[0],x.[1])
let Ia = stdin.ReadLine().Split() |> Array.map int
solve N X Ia |> stdout.WriteLine

方針¶

入力の配列が既にソートされていて必ず要素が存在する前提の問題です. 入力のソートは絶対に必要で, 後者は探索処理として適切な仕様決めが必要です. ここでは二分探索の結果をOptionにし, Option.defaultValue (-1)でモノがない場合は決して存在しない配列の添字-1を返すとします.

解説¶

命令型の言語ではwhileで処理する方が多いように思います. ここでは再帰関数で処理します. 二分探索はアルゴリズムのどの本にも載っているため細かい解説は省略します.

1
2
3
4
5
6
7

  let rec binSrch l r =
    let m = (l+r)/2
    if r<l then None
    elif Ia.[m]=X then Some m
    elif X<Ia.[m] then binSrch l (m-1)
    else binSrch (m+1) r
  binSrch 0 (N-1) |> Option.map ((+) 1) |> Option.defaultValue (-1)

最後のOption.map ((+) 1)だけ注意します. これは適合する配列の値が得られたelif Ia.[m]=X then Some mでmを返した点に対する修正です. 0-originのF#の配列の添字としてはmである一方, 問題では1-originであるためその分を加算処理しています.