【競プロからの学び】最も近い値を探す→bsearchが高速

TL;DR

タイトルの通り。
配列内から最も近い値を探す→bsearchが高速に動作する。
二分探索なので。

競技プログラミン初心者による、自分向け備忘の記事。

問題

https://atcoder.jp/contests/typical90/tasks/typical90_g
こちらの問題を解いている際のお話。

やりたいことの１つが以下の操作↓

• 「整数によって構成される配列a」と「定数b」を用意。
• 「aの中からbに最も近い値を探す(絶対値が最も小さい値を探す)」

例）
a = [1,5,19,7]
b = 8
=> answer = 7

自分の考え

  a.each do |i|
    b_arr << (a[i] - b).abs
  end
  puts b_arr.min

これだと計算が遅い。。。
i個分の差分計算の後にソートをしているので。。。

ほかの方の答え

  a.sort
  idx = a_arr.bsearch_index {|x| x >= b }

  if idx.nil?
    small = (a_arr[n-1] -b).abs
  elsif idx == 0
    small = (a_arr[0] -b).abs
  else
    small = [(a_arr[idx] - b).abs, (a_arr[idx-1] - b).abs].min
  end

これだと計算がはやい！
aをソートさえしてしまえば、
二分探索してindexの値で場合分けして値を出すのみ。

理由はたぶんこう？

計算量比較で、

• 線形探索は(n+1)/2
• 二分探索はlog2(n)

なので、確かに早くなりそうな気がする。

細かいところまでは調べ切れていないですが。。。

心優しい方、コメントで教えてください…！