Найти [j] = j за O (log n) время

Question

Как я могу найти, если отсортированный массив имеет элемент a [j] = j за O (log n) времени? (Без дубликатов)

Answer 1

Если массив состоит из целых чисел и не может содержать дубликаты, вы можете просто использовать двоичный поиск.

Например, скажем, у нас есть массив:

a[0] == -30
a[1] == 1
a[2] == 200
a[3] == 200
a[4] == 204
a[5] == 205
a[6] == 206
a[7] == 207

• Сначала попробуйте[floor (avg (0,7))] (то есть a [3]).Это равно 200. 200 слишком велико.
• Итак, перейдите к нижней половине.Попробуйте [floor (avg (0,2))] (то есть a [1]).Это равно 1. Ура!

Ваш бинарный поиск либо успешно найдет j, для которого a [j] == j, либо завершится неудачей из-за нехватки мест для поиска.Поскольку бинарный поиск - это O (log n), в течение этой временной сложности вы будете знать значение j или то, что такого j не существует.

Обратите внимание, что если несколько значений j удовлетворяют условию, вы просто найдетепроизвольный из них.

Answer 2

Если он может содержать повторяющиеся значения или это массив с плавающей точкой, вы не можете. Контрпример: a [2k] = 2k + 1, a [2k + 1] = 2k + 1 или 2k + 2. В худшем случае вы должны проверить [2k + 1] для всех k.

Если это целочисленный массив и все значения различны, то вы выполняете бинарный поиск. Посмотрите на [1] -1 и [n] -n. Если они имеют одинаковый знак, ответ - нет. Если они имеют разные знаки, посмотрите на [n / 2] -n / 2. Это либо ноль (и тогда у вас есть ответ), либо один из интервалов (1, n / 2) или (n / 2, n) будет иметь разные знаки на концах. Возьмите этот интервал и повторите.

Answer 3

Предполагается, что дубликаты запрещены:

#include <stdio.h>

int
find_elt_idx_match( int *a, int lo, int hi )
{
  int elt, idx;
  while ( lo <= hi )
    {
      idx = lo + ( hi - lo ) / 2; /* Thanks, @andand */
      elt = a[ idx ];
      if ( elt == idx )
        {
          return 1;
        }
      if ( elt < idx )
        {
          lo = idx + 1;
        }
      else
        {
          hi = idx - 1;
        }
    }
  return 0;
}

int
main( void )
{
  int a[ 100 ];
  /* fill a */
  /* ... */
  printf( "idx:elt match? %c\n", find_elt_idx_match( a, 0, 99 ) ? 'y' : 'n' );
  return 0;
}

Answer 4

Если дубликаты не разрешены, и ваш список отсортирован в соответствии с очевидным порядком a [i]

Answer 5

public int getFirstMatchedIndex(int[] oArry)
        {            
            int i = 0;
            while(i < oArry.Length )
            {
                if (oArry[i] == i)
                    return i;
                else if (oArry [i] > i)
                    i=oArry [i];
                else
                    i++;

            }
            return -1;
        }