Поиск в массиве

Question

У меня есть массив int x [] и число.Мне нравится выполнять поиск по массиву так, чтобы x [i] + x [i + 1] = число.

Какой самый эффективный и быстрый способ в Java?

Answer 1

Вот псевдокод, это должно работать.Только n памяти читает.

buff1 = x[0]
buff2 = 0
for i = 1 to n - 1
    buff2 = x[i]
    if (buff1 + buff2) == number
      then
        MATCH
    endif
    buff1 = buff2
endfor

Answer 2

Если массив не отсортирован, и вы выполняете только несколько поисков, используйте метод phoxis. Ожидается, что он будет выполняться в O (n * k), где n - размер x, а k - количество поисков, которые вы не хотите делать.

Если массив отсортирован, мы знаем, что x [i] <= число / 2 и x [i + 1]> = число / 2. Используйте двоичный поиск , чтобы найти (последний) предшественник с номером / 2 + 1 и проверить, соответствует ли оно.

int i = binaryPredecessor(x , number/2 + 1);
if(x[i] + x[i+1] == number){
   return i;
}
else if(x[i-1] + x[i] == number){
   //The case where x[i] == number/2, and we found the last of two occurrences
   return i-1;
} else {
   //No match exists
   return -1;
}

Время выполнения - O (log (n) * k).

Если вы выполняете много поисков, возможно, стоит отсортировать массив и использовать описанный выше метод. Массив можно отсортировать в O (n * log (n)) [см. mergersort ]. Поэтому, если вы хотите выполнить больше операций поиска в журнале (n), стоит отсортировать массив. (Если k близко к log (n), проведите некоторое тестирование, чтобы увидеть, что лучше :))