пожалуйста, объясните мне эту функцию двоичного поиска

Question

ниже - код Apple для общего бинарного поиска. Я не очень хорошо разбираюсь в битах и ​​т. Д., Поэтому мне очень трудно это понять. Я прокомментировал в коде ниже части, которые я понимаю

1. Что такое база? это массив, содержащий значения?

2. если nremain - это число значений в массиве, которые не были проанализированы, почему мы меняем это право на 1 каждую итерацию?

3. такжеПожалуйста, помогите мне понять, что такое первая строка forloop. поэтому я предполагаю, что p указывает на среднюю точку остальных элементов, но я не получаю (nremain >> 1) * часть ширины. Что такое ширина? Каким образом умножение версии nremain с правами на 1 на ширину устанавливает указатель на среднюю точку?

4. знак> 0, когда клавиша> p и указатель должны перейти к следующему элементу. Как это достигается с помощью p + width? Опять же, зная, что такое ширина, было бы очень полезно.

5. Я получаю, что мы вычитаем из nremain значение 1 в конце каждой итерации, чтобы показать, что один элемент был проанализирован, но чтоточка nremain >> = 1 каждая итерация в этом случае?

Заранее спасибо! Я с нетерпением жду ответа от кого-либо.

void *apple_bsearch(const void *key, const void *base, size_t nmemb,  
               size_t width, int (*compar)(const void *, const void *)) {
    for (size_t nremain = nmemb; nremain != 0; nremain >>= 1) {
        void *p = (char *)base + (nremain >> 1) * width; // I don't get this
        // this is comparing key & where currently p is pointing
        int sign = compar(key, p); 
        if (sign == 0) { // if p and key are equal, sign is 0
            return p;
        }
        if (sign > 0) {  // when key > p, move right
            base = (char *)p + width;
            nremain--;
        }       
    }
    return NULL;
}

Answer 1

Я сделаю определенное предположение (на основании обоснованного предположения, которое я бы сказал):

1. nmemb - это число членов массива
2. width - эторавно sizeof(array[0])
3. base указывает на первый член массива, т.е. , base == array[0]
4. массив отсортирован (от наименьшего к наибольшемузначение)

Обратите внимание, что сдвиг вправо по сути представляет собой целочисленное деление (отбрасывает остаток, например , 3 >> 1 == 1).

Функция принимаетследующие аргументы:

• key, указатель на const void
• base, указатель на const void
• nmemb, переменная size_t
• width, переменная size_t
• compar, (указатель) на функцию с двумя аргументами (2x указатель на const void), которая возвращает int

Тот факт, что используются указатели на void, позволяет функции быть независимой от размера элементов массива (и, следовательно, быть универсальной).

Теперь давайте построчно.

1. Цикл for инициализирует nremain как nmemb и повторяется до nremain != 0 (или return). И в конце цикла он делит nremain на 2, округляя результат вниз (смещение вправо на 1).

2. p объявляется как указатель на void setпри базовом смещении на половину nremain (количество рассматриваемых элементов массива) умноженное на width. Таким образом, p будет указывать на конец левой половины массива. Например, если в массиве 7 элементов, на первой итерации p будет указывать на 4-й элемент. Приведение (char *) base просто гарантирует, что добавлено правильное количество байтов, при условии, что width == sizeof(array[0]), поскольку sizeof(char) == 1.

3. compar затем сравнивает p с key и в случае успеха p возвращается.

4. Если p < key, то base устанавливается для следующего члена после элемента, на который указывает p и 1 вычитаетсяот nremain. Вот объяснение, связанное с Eric Postpischil : «Предыдущее присваивание p эффективно разбивает массив на три части: элемент, на который указывает p, элементы ранее, и элементы после этогоЧисло элементов ранее nremain>>1, число точно в p равно 1, а число после него (nremain-1)>>1. Например , если nremain равно 12, частиимеют 6, 1 и 5 элементов. Вычитая 1 из nremain в этот момент, вы гарантируете, что он будет правильно установлен шагом nremain >>= 1 для следующей итерации. "

5. Повтор.

6. Если мы не найдем значение и не выйдем из цикла for (обратите внимание, что когда nremain == 1 в конце цикла nremain >> 1 == 0), верните NULL.

Возможно, я ошибаюсь в некоторых предположениях, поэтому вы захотите отработать код, изменив их;). Надеюсь, это поможет!