Линейный поиск, который прыгает м мест

Question

Вот мой псевдокод:

LinearSearch(List, key, m):
    while (m < List.length):
       if (m==key):             // key is found
          return m
       else if (m < key):       // key is larger than index
           m = m + m
       else:                    // key is smaller than index
           m = m - 1
    return NIL

Но я не думаю, что это правильно, так как кажется неправильным, если ключ находится между List.length-m и List.length.

Может кто-нибудь сказать мне, что не так, пожалуйста?

Мне также хотелось бы, чтобы сложность этого алгоритма была временной, в 3 случаях:

worstcase when successful search
worst case when unsuccessful search
average case

Спасибо

Answer 1

Вы сравниваете m с key несколько раз.Вы, вероятно, должны сравнивать list[m] с key.

Кроме того, если m начинается с 0, оно никогда не будет 0 (0 + 0 = 0).

Другая проблема - та, которую вы перечислили.Скажите list это {1 2 3 4 5 6 7 8 9}, key это 9, и вы начинаете с m=1.m станет 2, затем 4, затем 8. List[m] все еще меньше, чем ключ, поэтому m снова удваивается до 16, и в этот момент выходит из цикла, потому что m больше не меньше длинысписок.Есть несколько способов исправить это, но ни один из них не будет очень сложным, если вы поймете проблему, с которой вы столкнулись.