Улучшить tempral сложность алгоритма

Question

У меня простая функция

bool function(int*a,int n) 
{ 
    for(int i = 0; i<=n-1;i++) 
    if(a[i]==i) 
     return true; 
    return false; 
} 

, где a является отсортированный вектор, который содержит различные элементы и п является размер вектора.

Мне нужно улучшить временную сложность этого алгоритма. Моя первая мысль заключалась в использовании бинарного поиска, но я могу выяснить, как сделать рекурсию работой в этом случае. В основном функция проверяет наличие элемента в отсортированном массиве, для которого индекс равен элементу.

Answer 1

Не предлагая полного решения, вы на правильном пути с бинарным поиском. Некоторые советы:

The A [я] 's различны и увеличивающиеся целые

Если [я] больше, чем я в какой-то момент, что это значит для [J], где J> я? (начинаются с [i + 1] по сравнению с i + 1)

Аналогично, если a [i] < i, что это означает для [j] для j < i?

Сложите эти факты вместе. Что это значит, когда a [i] «пересекает» i? Как вы находите, где это происходит?