CKTIS / C
Двоично търсене и lower bound на C
Двоичното търсене многократно разделя сортиран интервал за търсене наполовина. Примерът реализира lower bound: индекса на първия елемент, който не е по-малък от ключа, или n, ако такъв няма. Разглежда дубликати, празен вход и безопасно изчисляване на средата.
Версия: C23; repository compiler flag, production runtime not attested
Синтаксис
size_t lower_bound_int(const int *a, size_t n, int key);Двоичното търсене избира средата на интервал и отхвърля половината, която не може да съдържа търсения резултат. Предварителното условие за сортиран вход тук означава, че a[0..n) е сортиран в ненамаляващ ред според същото сравнение, което използва търсенето. Функцията не проверява това условие; несортиран вход може да доведе до грешен резултат.
Примерната функция lower_bound_int реализира lower bound: връща първия индекс pos, за който е изпълнено a[pos] >= key, или n, ако такъв няма. При дубликати тя посочва първото срещане. Самият индекс не потвърждава, че ключът присъства: използвайте проверката pos < n && a[pos] == key. Оценяването с късо съединение не позволява на тази проверка да прочете a[n].
Цикълът поддържа полуотворения интервал [lo, hi): елементите преди lo са по-малки от key, а елементите от hi до n не са по-малки от key. Операторът hi = mid запазва възможния първи резултат, докато lo = mid + 1 пропуска твърде малък елемент. Изразът lo + (hi - lo) / 2 избягва препълване при събиране на границите. Когато lo == hi, и двете граници определят резултата.
За n > 0 a трябва да предоставя поне n валидни елемента; те не бива да се променят по време на търсенето. За n == 0 тази реализация приема NULL и връща 0, без да чете памет. При масив времето е O(log n) за n >= 2, а допълнителната памет е O(1); предварителното сортиране не е включено. C23 е целта на флаговете на компилатора в хранилището, а не удостоверение за продукционната среда за изпълнение.
Примери
#include <stddef.h>
#include <stdio.h>
static size_t lower_bound_int(const int *a, size_t n, int key)
{
size_t lo = 0;
size_t hi = n;
while (lo < hi) {
size_t mid = lo + (hi - lo) / 2;
if (a[mid] < key) {
lo = mid + 1;
} else {
hi = mid;
}
}
return lo;
}
int main(void)
{
const int a[] = {1, 3, 3, 7};
const size_t n = sizeof a / sizeof a[0];
const int keys[] = {3, 4, 9};
for (size_t i = 0; i < sizeof keys / sizeof keys[0]; ++i) {
size_t pos = lower_bound_int(a, n, keys[i]);
int found = pos < n && a[pos] == keys[i];
printf("key=%d pos=%zu found=%d\n", keys[i], pos, found);
}
printf("empty pos=%zu\n", lower_bound_int(NULL, 0, 3));
return 0;
}
Резултат
key=3 pos=1 found=1 key=4 pos=3 found=0 key=9 pos=4 found=0 empty pos=0
Показаният код и заявеният резултат са проверени в изолирана среда по метода, записан в доказателството за проверка на тази точна версия.