Найти индекс массива и значение, которое равно

Question

У меня есть отсортированный массив из n элементов. Значения могут быть отрицательными или положительными.

Особенностью этого массива является то, что из n элементов существует один конкретный элемент, где [x] = x и остальные данные не удовлетворяют условию.

Есть ли лучший способ найти такой «х», кроме цикла всего массива.

Пусть мой массив [-2999, -33,0,2,4,67,654] Здесь [4] = 4, а остальное не соответствует такому критерию ..

Answer 1

Поскольку массив уже отсортированный, вы можете использовать бинарный поиск, который является O (lgn), чтобы найти элемент.

Вы также можете игнорировать все отрицательные элементы, потому что индекс не может быть отрицательным.

http://en.wikipedia.org/wiki/Binary_search_algorithm

Answer 2

вы можете использовать это. Это O (N).

for(i=0;i<MAX;i++){ 
    if(i==array[i]){//do something} 
} 

Если массив сортируется в порядке убывания использовать

for(i=MAX-1;i>=0;i11){ 
    if(i==array[i]){//do something} 
} 

Здесь МАХ размер массива