問題名の通り二分探索を用いると、入力を受け取る部分を除いて計算量 \(O(\log N)\) で解くことができます。

クエリ形式を取っていないので計算量 \(O(N)\) の線形探索でもACとなりますが、練習問題として取り組む場合は二分探索を用いて実装してみてください。