入力で正の整数Nを与え、1からNまで各要素の差が1の配列Aを作成する
1からNまでの間の整数で探索する値をランダムに生成し、探索する値を超えないが最も値が近い配列Aの要素を見つけるプログラムを書いています。

具体的なアルゴリズムの用途には、衝撃吸収材の精度を測るため、高い所から生卵を落として割れない限界の高さを調べる試験を想定しています。
高さは最大でNmで、試験に使える生卵に制限があるときに探索回数に制限があると考えられます。

探索回数に制限がない以下のプログラムの場合、計算量はO(logN)ですが、探索回数に制限があるプログラム2の場合、どんなに速くてもO(N)が最速になるでしょうか。

探索回数に制限があるプログラム2の場合、他にもっと計算量が速くなるアルゴリズムがあれば教えていただきたいです。

単純な二分探索で一致する値を配列A内から見つけるプログラム

def solution(N):
    A = []
    for i in range(1, N+1, 1):
        A.append(i)

    target = random.randint(1, N)

    lo = 0
    hi = len(A)-1

    while hi>lo:
        mid = round((hi+lo)/2)
        print(mid)

        if A[mid] == target:
            return "位置" + str(mid) + "に存在する"

        elif A[mid] >= target:
            hi = mid -1

        elif A[mid] < target:
            lo = mid + 1

    return "None"

プログラム2
実行例

#6mの高さから落とせる卵は2個まで
#1/3ずつの高さから１つ目を落としてみる
solution(6, 3, 2)

コード

import random

#探索のうちに探している値を超えていいのはlife-1回までとする

    def solution(N,d,l):
        A = []
        for i in range(1, N+1, 1):
            A.append(i)

        target = random.randint(1, N)
        life = l

        #分母
        denominator = d
        #分子の候補
        numerator = []
        for j in range(1, N-1, 1):
            numerator.append(j)

        #指定された分割数のうち最も小さい位置の値をhiとする
        #k=3なら1/3、K=6なら1/6
        lo = 0
        hi = len(A) * (numerator[0]/denominator)

        #lifeが１になる直前の要素番号を記録する変数
        r = 0

        for x in range(1, len(numerator), 1):
            if life > 1:
                if A[hi] >= target:
                    life = life - 1:
                    r = hi
                else:
                    hi = len(A) * (numerator[x]/denominator)


        #lifeが１になったらlifeが１になる直前までを線形探索
        S = []
        for t in range(r):
            S.append(t)

        #配列内要素とtargetの間の差、仮に初期値100とする
        diff = 100

        #lifeが１になる直前までの区間
        for u in range(len(S)):
            if targe > S[u] and abs(target - S[u]) < diff:
                place = u

            return "位置" + str(place) + "に存在する"