您的方法的时间复杂度为O（n）

查询时间复杂度O（1）解决方案

const int n = 6;
bool arr[n] = { false,true,false,true };
int next_index[n];

int get_next_true(int index) {
  return next_index[index];
}

int main() {
  int true_index = -1;
  for (int i = n - 1; i >= 0; i--) {
    next_index[i] = true_index;
    if (arr[i] == true)
      true_index = i;
  }
  for (int i = n - 1; i >= 0; i--) {
    if (next_index[i] == -1)
      next_index[i] = true_index;
    else
      break;
  }
  printf("%d\n",get_next_true(2));
}

查询时间复杂度O（log ₂ n）解决方案

您可以维护arr的前缀总和（将true视为值1），然后使用二进制搜索来查找下一个真值的索引。

一个简单的演示

const int n = 6;
bool arr[n] = { false,true };
int prefix[n];
bool isNewRound = false;

int get_next_true(int index) {
  int pos = std::upper_bound(prefix + index + 1,prefix + n,prefix[index]) - prefix;
  if (pos != n)
    return pos;
  isNewRound = true;

  pos = std::upper_bound(prefix,prefix + index + 1,0) - prefix;
  if (arr[pos] == false)
    return -1; // Not Found

  return pos;
}

另外，请记住在调用get_next_true之前进行一些预处理：

prefix[0] = arr[0];
for (int i = 1; i < n; i++) {
  prefix[i] = arr[i] + prefix[i - 1];
}

查询和修改时间复杂度为O（log ₂ n）

请注意，如果arr不是固定数组（您可能需要对其进行修改），则将需要使用诸如segment tree之类的数据结构。

我不了解发布的代码意图，但是如果任务是

  

使用真实值查找下一个数组索引

一个简单的解决方案（可测试的here）可能是

template <class It>
constexpr size_t find_index_of_next_true(It first,It last,size_t index)
{
    size_t size = std::distance(first,last);
    return size <= index
        ? size
        : std::distance(first,std::find(first + index + 1,last,true));
}

当然是O（N），因为这是std::find的时间复杂度，但是OP没有提到它们的数组有多大。

时间复杂度O（1），其中O（N）个额外空间

首先，我们可以在数组保存真值的地方存储所有索引，从而可以恒定时间访问下一个索引。预处理（构造索引数组）仍然需要线性时间，因此，当您要遍历 true 索引多次时，这种方法很有意义。

此代码显示了静态版本，而动态代码则需要O（N）时间来修改数组中的值。

#include <array>
#include <vector>

template <unsigned N>
class BoolArray {
public:
  using true_iterator = std::vector<unsigned>::const_iterator;

  BoolArray(std::array<bool,N> &&Init) : Data(std::move(Init)) {
    init();
  }

  true_iterator tbegin() const {
    return TrueValues.begin();
  }

  true_iterator tend() const {
    return TrueValues.end();
  }

  bool operator[](unsigned Index) {
    return Data[Index];
  }

private:
  void init() {
    TrueValues.reserve(N);
    // O(N) time to pre-process the data
    for (unsigned i = 0; i < N; ++i) {
      if (Data[i]) {
        TrueValues.push_back(i);
      }
    }
  }

  std::array<bool,N> Data;
  // extra O(N) space for fast fetching of the next index
  std::vector<unsigned> TrueValues;
};

时间复杂度O（N），其中有O（1）个额外空间

这是一种更直接的方法。在我们中断的地方进一步迭代，一直迭代到最后。

实现的迭代器只是一个原型，可以实现为双向。

#include <array>

template <unsigned N>
class BoolArray {
public:
  BoolArray(std::array<bool,N> &&Init) : Data(std::move(Init)) {}

  class true_iterator : public std::forward_iterator_tag {
  public:
    true_iterator(const true_iterator &) = default;
    true_iterator &operator=(const true_iterator &) = default;
    true_iterator(true_iterator &&) = default;
    true_iterator &operator=(true_iterator &&) = default;

    unsigned operator*() const {
      // O(1) for random-access iterators,which is true for
      // array iterators (it's just a difference between indices)
      return std::distance(Data.begin(),Iterator);
    }

    true_iterator &operator++() {
      ++Iterator;
      skipFalseValues();
      return *this;
    }
    true_iterator &operator++(int) {
      true_iterator tmp(*this);
      operator++();
      return tmp;
    }

    bool operator==(const true_iterator& rhs) const {
      return Iterator == rhs.Iterator;
    }
    bool operator!=(const true_iterator& rhs) const {
      return Iterator != rhs.Iterator;
    }

  private:
    using UnderlyingIterator = typename std::array<bool,N>::const_iterator;

    void skipFalseValues() {
      // O(N) time to find next true element
      for (;Iterator != Data.end() and not *Iterator; ++Iterator) {};
    }

    friend class BoolArray<N>;
    true_iterator(const std::array<bool,N> &Data,UnderlyingIterator Current)
      : Data(Data),Iterator(Current) {
      skipFalseValues();
    }

    const std::array<bool,N> &Data;
    UnderlyingIterator Iterator;
  };

  true_iterator tbegin() const {
    return {Data,Data.begin()};
  }

  true_iterator tend() const {
    return {Data,Data.end()};
  }

  bool operator[](unsigned Index) {
    return Data[Index];
  }

private:
  std::array<bool,N> Data;
};

测试

在两种情况下，以下代码：

int main() {
  constexpr unsigned Size = 6;
  BoolArray<Size> TestArray{ {false,true} };
  for (auto It = TestArray.tbegin(),End = TestArray.tend(); It != End; ++It) {
    std::cout <<
      (TestArray[*It] ? "true" : "false") << " at index " << *It << std::endl;
  }
}

产生以下输出：

true at index 1
true at index 5