uraway https://blog.hatena.ne.jp/uraway/ 文系プログラマー https://uraway.hatenablog.com/ algorithm バイナリサーチ 問: ソートされた数値の配列と数値targetを受け取り、配列中のtargetのインデックスを求める。その際、バイナリサーチを用いること。 アルゴリズム実装 $O(\log n)$ 配列の要素数をnとしたとき、left=0、right=nの変数を作る。また、leftとrightの中央の位置をmidとする。 array[mid] === targetならtargetが見つかったとして探索終了。left >= rightなら見つからなかったとして探索終了。 array[mid] > targetならtargetは配列の左半分にあるので、right=mid-1として0へ array[… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Furaway.hatenablog.com%2Fentry%2F2019%2F12%2F18%2F080000" title="バイナリサーチ - 文系プログラマー" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%7B%5Cdisplaystyle%0A%5Cbegin%7Baligned%7D%0A1%20%26%3D%20n%28%5Cfrac%7B1%7D%7B2%7D%29%20%5Ek%20%5C%5C%0An%20%26%3D%202%5Ek%20%5C%5C%0Ak%20%26%3D%20%5Clog_2%20n%20%0A%5Cend%7Baligned%7D%0A%7D Hatena Blog https://hatena.blog 2019-12-18 08:00:00 rich https://uraway.hatenablog.com/entry/2019/12/18/080000 1.0 100%