Когда использовать «=» в режиме двоичного поиска?

Question

Я довольно запутался в сценариях, когда следует использовать = в двоичном поиске. Например, это то, что я нашел из вики, в котором он используется в то время как (imin <= imax)

int binary_search(int A[], int key, int imin, int imax) 
{ 
    // continue searching while [imin,imax] is not empty 
    while (imin <= imax) 
    { 
    int imid = midpoint(imin, imax); 
    if (A[imid] == key) 
    return imid; 
    else if (A[imid] < key) 
    imin = imid + 1; 
    else   
    imax = imid - 1; 
    } 

    return KEY_NOT_FOUND; 
} 

Однако, я также нашел много кода, используя что-то вроде

while (imin < imax) 

Мои вопросы: что такое вы хотите использовать = или нет? Любая причина?

Большое спасибо!

Answer 1

(А < В) будет истинным, если и только если А меньше В

(А < = В) будет истинным, если и только если А меньше или равно В

Таким образом, вы используете '< =' или '> =', когда вы хотите, чтобы условие оценивалось как true, если два сравниваемых значения равны. Если равные значения не должны удовлетворять условию, то вы используете «<» или «>».

Например, после выполнения следующего кода, значение переменной «Count» будет 2, потому что код внутри «а» блок будет выполняться дважды:

imin = 1; 
    imax = 2; 
    count = 0; 
    while (imin <= imax) 
    { 
     imin = imin + 1; 
     count = count + 1; 
    } 

Но в следующем коде , значение «count» будет только 1 после выполнения, потому что код будет выполняться только один раз. Единственное отличие - оператор «<».

imin = 1; 
    imax = 2; 
    count = 0; 
    while (imin < imax) 
    { 
     imin = imin + 1; 
     count = count + 1; 
    } 

Answer 2

Примечание эти два алгоритма на wiki:

Итерационный бинарный поиск:

int binary_search(int A[], int key, int imin, int imax) 
{ 
    // continue searching while [imin,imax] is not empty 
    while (imin <= imax) 
    { 
     // calculate the midpoint for roughly equal partition 
     int imid = midpoint(imin, imax); 
     if (A[imid] == key) 
     // key found at index imid 
     return imid; 
     // determine which subarray to search 
     else if (A[imid] < key) 
     // change min index to search upper subarray 
     imin = imid + 1; 
     else   
     // change max index to search lower subarray 
     imax = imid - 1; 
    } 
    // key was not found 
    return KEY_NOT_FOUND; 
} 

Итерационный бинарный поиск с отложенным обнаружения равенства:

int binary_search(int A[], int key, int imin, int imax) 
{ 
    // continually narrow search until just one element remains 
    while (imin < imax) 
    { 
     int imid = midpoint(imin, imax); 

     // code must guarantee the interval is reduced at each iteration 
     assert(imid < imax); 
     // note: 0 <= imin < imax implies imid will always be less than imax 

     // reduce the search 
     if (A[imid] < key) 
     imin = imid + 1; 
     else 
     imax = imid; 
    } 
    // At exit of while: 
    // if A[] is empty, then imax < imin 
    // otherwise imax == imin 

    // deferred test for equality 
    if ((imax == imin) && (A[imin] == key)) 
    return imin; 
    else 
    return KEY_NOT_FOUND; 
} 

У вас есть три случая для рассмотрения, когда imin < imax, imin == imax и imin > imax. Первый алгоритм имеет дело с меньшим и равенством внутри цикла while, тогда как во втором алгоритме случай равенства переносится на оператор if. Как указано в wiki:

Итеративная и рекурсивная версии принимают три пути на основе сравнения ключей: один путь для меньшего, один путь для большего и один путь для равенства. (Есть две условные ветви.) Путь для равенства берется только тогда, когда запись окончательно согласована, поэтому ее редко принимают. Этот путь ветки может быть перемещен за пределы цикла поиска в отложенном тесте для версии алгоритма равенства.

Подход с отложенным обнаружением отклоняет возможность раннего завершения при обнаружении соответствия, поэтому поиск будет проходить по логическим ошибкам log2 (N). В среднем успешный поиск по раннему завершению не сэкономит много итераций. Для больших массивов, которые имеют мощность 2, экономия составляет около двух итераций.Половина времени найдено совпадение с одной итерацией влево; одна четверть времени с двумя итерациями слева, одна восьмая с тремя итерациями и т. д. Сумма бесконечной серии равна 2.

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

Таким образом, использование либо <= в цикле в то время, или просто <, будет зависеть от вашего выбора реализации.