目的の値を超えてもいい回数をlife回とすると、life == 1 の時 O(N) ですが、life > 1の時 O(N) より速く解けます
例えば life == 2 の場合
最初に目的の値を超えるまで、sqrt(N) 間隔で調べていき、目的の値を超えたら、最後に超えなかったところから 1 ずつ調べていきます
この時、最初に超えるまでの比較が、O(N / sqrt(N)) ステップかかり、その後のステップが O(sqrt(N)) かかるので全体として O(sqrt(N)) で解けます
これを一般化すると、
life == n (n > 1) の場合
最初に目的の値を超えるまで、step 間隔で調べていき、超えたら、最後に超えなかったから超えたところまでの区間を life <- n - 1 として探索を行うと考えることができます
この時 step <- N ** ((life - 1) / life) とすると、計算量は O(life * (N ** (1 / life))) になります。
この上界の関数は life == log(N) で最小になるので、それより大きな life の時は、life ← log(N) とすることで O(logN) になります。
サンプルコード(質問内の想定用途をもとにコードにしています。質問内のコードとは仕様が違うので注意してください。詳しくはコメント参照)
import random
import math
#昇順に並んだリストAから、targetを超えない最大の値を見つける。ただしtargetの値を超える比較を行えるのはちょうどlife回まで。
#リストのすべての要素がtargetを超えるとき -1
def solution(A, target, life):
if life > math.log(len(A)):
life = max(1, int(math.log(len(A))))
lo = 0
hi = len(A)
#比較回数と失敗回数の記録用変数、compとfail
comp = 0
fail = 0
for l in range(life, 0, -1):
step = round((hi - lo) ** ((l - 1) / l))
for t in range(lo, hi, step):
comp += 1
if A[t] > target:
fail += 1
hi = t + 1
break
else:
lo = t + 1
if (hi == lo):
break
print("比較回数 = " + str(comp) + ", 失敗回数 = " + str(fail))
if lo == 0:
return -1
else:
return A[lo - 1]
size = 1000000
maxLife = 3
target = random.randint(0, size)
A = range(1, size)
print("target = " + str(target) + ", answer = " + str(solution(A, target, maxLife)))
計算量をもっと厳密に計算したり、目的の値を超えるまでの比較の間隔 step を比較ごとに短くしていくことで計算量が減らせそうですが、複雑なのでやってません。