[Alexandroppolus]

j0hnik,
опять забыл важное условие числа в массиве не повторяются, все разные

а в целом сразу понятно куда копать - двоичный (или даже интерполяционный) поиск, a[i] >= i - смотрим влево, a[i] < i - вправо