二分探索の計算量の求め方について

下記の二分探索の計算量は、while文がlogN回実行されるからO(logN)ということになっていると思います。ですが、各while文の中でリストにアクセスする必要があって、リストへのアクセスはO(N)の計算量がいるので、二分探索の実際の計算量はO(NlogN)になる気がするのですがどうなのでしょうか？
リストへのアクセスは実際にはCPU内部でキャッシュが使われるので、無視できる計算量になるみたいな話なのでしょうか？

python
1int binary_search(int v) {
2    /* 目的の index は [left, right) のどこかにある */
3    int left = -1;
4    int right = (int)a.size();
5
6    while (right - left > 1) {
7        int mid = left + (right - left) / 2;
8
9        /* a[mid] と v との大小関係に応じて候補区間を左右半分に分ける */
10        if (a[mid] >= v) right = mid; // 候補区間を [left, mid) に
11        else left = mid;              // 候補区間を [mid, right) に
12    }
13
14    /* left は条件を満たさない最大の値、right は条件を満たす最小の値になっている */
15    return right;
16}

quickquip

2021/03/31 01:29

言語タグを間違えていると思います。コード中にaの定義がありません。

行動規範の内容に同意します

回答2件

おそらく用語の混乱かと思います。
アルゴリズムの世界で単に「リスト」というと線形リストを指す場合が多いと思います。これは要素をポインタでつないでいくもので、アクセスには平均O(N)の時間がかかります。
一方、Pythonでいうリストはアルゴリズムの世界では配列と呼ばれるもので、各要素へのアクセスはO(1)で可能です。なので、二分探索の平均の計算量は O(log N)になります。二分探索の実装に線形リストを使うことには意味がないので通常やらないと思います。

投稿2021/03/31 01:43