Эффективный способ поиска элемента

Ответ 1

Вы можете выполнить линейный поиск с шагами, которые часто превышают 1. Важное замечание состоит в том, что, если, например, array[i] == 4 и 7 еще не появился, тогда следующий кандидат для 7 находится в индексе i+3. Используйте цикл while, который повторно переходит непосредственно к следующему жизнеспособному кандидату.

Вот реализация, слегка обобщенная. Он находит первое вхождение k в массиве (с учетом ограничения + = 1) или -1, если оно не встречается:

#include <stdio.h>
#include <stdlib.h>

int first_occurence(int k, int array[], int n);

int main(void){
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};
    printf("7 first occurs at index %d\n",first_occurence(7,a,15));
    printf("but 9 first \"occurs\" at index %d\n",first_occurence(9,a,15));
    return 0;
}

int first_occurence(int k, int array[], int n){
    int i = 0;
    while(i < n){
        if(array[i] == k) return i;
        i += abs(k-array[i]);
    }
    return -1;
}

выход:

7 first occurs at index 11
but 9 first "occurs" at index -1

Ответ 2

Ваш подход слишком сложный. Вам не нужно проверять каждый элемент массива. Первое значение 4, поэтому 7 не менее 7-4 элементов, и вы можете пропустить их.

#include <stdio.h>
#include <stdlib.h>

int main (void)
{
    int array[] = {4,5,6,5,4,3,2,3,4,5,6,7,8};
    int len = sizeof array / sizeof array[0];
    int i = 0;
    int steps = 0;
    while (i < len && array[i] != 7) {
        i += abs(7 - array[i]);
        steps++;
    }

    printf("Steps %d, index %d\n", steps, i);
    return 0;
}

Выход программы:

Steps 4, index 11

Изменить: улучшено после комментариев от @Raphael Miedl и @Martin Zabel.

Ответ 3

Вариант обычного линейного поиска может быть хорошим способом. Выберем элемент say array[i] = 2. Теперь array[i + 1] будет либо 1, либо 3 (нечетным), array[i + 2] будет (только положительные целые числа) 2 или 4 (четное число).

Продолжая так, шаблон можно наблюдать - array[i + 2*n] будет содержать четные числа, и поэтому все эти индексы можно игнорировать.

Кроме того, мы можем видеть, что

array[i + 3] = 1 or 3 or 5
array[i + 5] = 1 or 3 or 5 or 7

Итак, индекс i + 5 следует проверить следующим образом, а цикл while можно использовать для определения следующего индекса для проверки в зависимости от значения, найденного в индексе i + 5.

В то время как это имеет сложность O(n) (линейное время в терминах асимптотической сложности), оно лучше, чем обычный линейный поиск, с практической точки зрения, поскольку все индексы не посещаются.

Очевидно, что все это будет отменено, если array[i] (наша начальная точка) была нечетной.

Ответ 4

Подход, представленный Джоном Коулманом, - это то, на что надеялся интервьюер, по всей вероятности.
Если вы готовы пойти немного сложнее, вы можете увеличить ожидаемую длину пропусков:
Вызвать целевое значение k. Начните с первого значения элемента v в позиции p и вызовите разность k-v dv с абсолютным значением av. Чтобы ускорить поиск отрицательных результатов, загляните в последний элемент как другое значение u в позиции o: если dv × du отрицательно, k присутствует (если любое появление k приемлемо, вы можете сузить диапазон индексов здесь так, как это делается бинарный поиск делает). Если av + au больше длины массива, k отсутствует. (Если dv × du равно нулю, v или u равно k.)
Опускание значения индекса: проверьте, что ( "следующая" ) позиция, в которой последовательность может вернуться к v с k в середине: o = p + 2*av.
Если dv × du отрицательно, найдите k (рекурсивно?) От p + av до o-au; если оно равно нулю, то u равно k в точке o.
Если du ​​равно dv, а значение в середине не k, или au превышает av,
или вы не можете найти k от p + av до o-au,
пусть p=o; dv=du; av=au; и держит зондирование.
(Для полного флеш-фрейма к текстам 60-х годов просмотрите курьером. Моя "1-я 2-я мысль" должна была использовать o = p + 2*av - 1, что исключает du равно dv.)

Ответ 5

ШАГ 1

Начните с первого элемента и проверьте, не ли это 7. Скажем, c - это индекс текущей позиции. Итак, изначально c = 0.

ШАГ 2

Если оно равно 7, вы нашли индекс. Это c. Если вы достигли конца массива, вырывайтесь.

ШАГ 3

Если это не так, то у 7 должно быть по крайней мере |array[c]-7| позиции, потому что вы можете добавлять только единицы за индекс. Поэтому добавьте |array[c]-7| к вашему текущему индексу, c и снова перейдите к STEP 2., чтобы проверить.

В худшем случае, когда есть альтернативные 1 и -1s, временная сложность может достигать O (n), но средние случаи будут доставлены быстро.

Ответ 6

Здесь я даю реализацию в java...

public static void main(String[] args) 
{       
    int arr[]={4,5,6,5,4,3,2,3,4,5,6,7,8};
    int pos=searchArray(arr,7);

    if(pos==-1)
        System.out.println("not found");
    else
        System.out.println("position="+pos);            
}

public static int searchArray(int[] array,int value)
{
    int i=0;
    int strtValue=0;
    int pos=-1;

    while(i<array.length)
    {
        strtValue=array[i];

        if(strtValue<value)
        {
            i+=value-strtValue;
        }
        else if (strtValue==value)
        {
            pos=i;
            break;
        }
        else
        {
            i=i+(strtValue-value);
        }       
    }

    return pos;
}

Ответ 7

Вот решение стиля "разделяй и властвуй". За счет (много) большего объема бухгалтерии мы можем пропустить больше элементов; вместо сканирования слева направо, тест в середине и пропустить в обоих направлениях.

#include <stdio.h>                                                               
#include <math.h>                                                                

int could_contain(int k, int left, int right, int width);                        
int find(int k, int array[], int lower, int upper);   

int main(void){                                                                  
    int a[] = {4,3,2,3,2,3,4,5,4,5,6,7,8,7,8};                                   
    printf("7 first occurs at index %d\n",find(7,a,0,14));                       
    printf("but 9 first \"occurs\" at index %d\n",find(9,a,0,14));               
    return 0;                                                                    
}                                                                                

int could_contain(int k, int left, int right, int width){                        
  return (width >= 0) &&                                                         
         (left <= k && k <= right) ||                                            
         (right <= k && k <= left) ||                                            
         (abs(k - left) + abs(k - right) < width);                               
}                                                                                

int find(int k, int array[], int lower, int upper){                              
  //printf("%d\t%d\n", lower, upper);                                            

  if( !could_contain(k, array[lower], array[upper], upper - lower )) return -1;  

  int mid = (upper + lower) / 2;                                                 

  if(array[mid] == k) return mid;                                                

  lower = find(k, array, lower + abs(k - array[lower]), mid - abs(k - array[mid]));
  if(lower >= 0 ) return lower;                                                    

  upper = find(k, array, mid + abs(k - array[mid]), upper - abs(k - array[upper]));
  if(upper >= 0 ) return upper;                                                  

  return -1;                                                                     

}