возврат стека к определенному фрагменту не меняет его флаг isVisible на true

Похоже, вы неправильно поняли временную сложность требуемого решения. Хуже дело не O(n), это O(log(n)). Это потому, что во время каждого прохода вы в следующий раз выполняете только половину массива.

Вот пример C ++ и проверьте, что для всего массива из 11 элементов требуется всего 3 проверка.