Среднее количество сравнений для отказа в этом алгоритме последовательного поиска?

Question

Алгоритм:

public boolean search(int[] A, int target) 
{ 
    for(int i=0;i<A.length;i++) 
    { 
     if(target==A[i]) return true; 
     if(target<A[i]) return false; 
    } 
    return false; 
} 

У меня возникли проблемы с пониманием этой проблемы - я знаю, что это имеет какое-то отношение к серии, но введение двух сравнений на итерации действительно имеет меня в тупик. Может кто-нибудь помочь мне и объяснить это мне?

Answer 1

Как я привык смотреть на это было:

думать о лучшем случае, Что можно меньше сравнения вы можете иметь? что было бы:

target==A[0] //first element 

подумайте о своем худшем случае, какие наибольшие сравнения вы можете иметь? то есть:

target==A[A.length-1] ///last elements or not found 

так какой будет наш средний случай?

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

, если вы ищете определенный номер число они средних сравнений может быть

3 сравнения «для comparrison, цель == A [я], цель < А [я] раз п/2», который является нашим среднего количества comparissons

, если вы хотите, чтобы проверить это вы можете сделать счетчик и увеличить 1 каждый раз вы делаете сравнение в вашем алгоритме