番兵さんはオチじゃなくて線形探索法の中に番兵法っていうものがあります。
要するに「ここが最後尾ですよ」という目印となるデータを用意して、そのデータを見つけた段階でデータはここで終了ってことを判断します。
ちなみに先頭から順番に探索するので、N個のデータの最大探索回数はそのまんまのN回となって平均は最初で見つける場合(1回)と最後に見つける場合(N回)の平均なので(1+N)/2となります。
ループ回数が1回なので計算量(オーダ)としてはO(N)です。
いろんなパワーに繋がるので、ちょっとだけクリック宜しくお願いします。
最後に、いつも拝見・応援してくださる皆様どうもありがとうございます。