アクセス時間が一定でない配列の2分探索（2）

アクセス時間が配列のインデックスに比例する場合に、次のインデックスの選び方を次のようにする。

half = int(start * (1 - s) + end * s);

if half == start:

    half = start + 1;

halfという識別子はちょっとおかしいが気にしない。このsが0.5なら単純な2分探索になり、0.5より小さければ真ん中より小さいインデックスを選ぶことになる。
sを0.45から0.55まで振ってみた。

def find(start, end, x):

    if end - start == 1:

        return 0

    else:

        half = int(start * (1 - s) + end * s);

        if half == start:

            half = start + 1;

        if half < x:

            return find(half, end, x) + half

        else:

            return find(start, half, x) + half
def mean_time():

    n = 1024

    sum = 0

    for x in range(1, n + 1):

        sum += find(0, n, x)

    

    return sum / float(n)
s = 0.45

while s < 0.551:

    print "%.3f %.2f" % (s, mean_time());

    s += 0.005

0.450 5228.61

0.455 5215.55

0.460 5214.26

0.465 5218.07

0.470 5210.90

0.475 5212.17

0.480 5209.78

0.485 5204.12

0.490 5203.89

0.495 5204.68

0.500 5120.00

0.505 5125.50

0.510 5131.40

0.515 5137.10

0.520 5145.04

0.525 5153.04

0.530 5160.48

0.535 5168.09

0.540 5176.90

0.545 5184.49

0.550 5192.06

微妙だが、0.5が最小となっている。