firstIndex が先頭から X% のあたりに存在してることを期待しても O(n) で、先頭から M 個以内に存在することを期待してる場合だけが O(1) な気が。