Алгоритм поиска пика числовой последовательности

Имеется алгоритм поиска пика последовательности, где nel - количетво элементов последовательности, а *less - указатель на функцию сравнивания двух элементов последовательности.
Язык Си:
unsigned long peak(unsigned long nel, int(*less)(unsigned long i, unsigned long j)) { if (nel < 3) return less(0, 1); for (unsigned long k = 1; k < (nel - 1); k++) { if(less(k-1, k) && less(k+1, k)) return k; } }
Он работает для небольших по длине числовых последовательностей, но при подключения функции к программе:
int less(unsigned long i, unsigned long j) { if (i == j) return 0;
if (i < j) { if (j <= 11241155978086311589UL) return 1; if (i >= 11241155978086311589UL) return 0; return (11241155978086311589UL-i) < (j-11241155978086311589UL); }
if (i <= 11241155978086311589UL) return 0; if (j >= 11241155978086311589UL) return 1; return (11241155978086311589UL-j) < (i-11241155978086311589UL); }
unsigned long peak(unsigned long, int (*)(unsigned long, unsigned long));
int main(int argc, char **argv) { unsigned long i = peak(13356955260197607378UL, less); if (i == 11241155978086311589UL) { printf("CORRECT
"); } else { printf("WRONG
"); } return 0; }
Программа выполняется очень долго. Нужна идея оптимизации функции peak(), чтобы она работала как для коротких последовательностей, так и для данной выше программы.
Функция peak должна возвращать индекс любого найденного пика.

Ответ

Для решения задачи можно использовать дихотомию. Кроме того "unsigned long" насколько я знаю 32-битный, потому нужно исправить в коде на uint64_t или unsigned long long. Вот я написал решение на C (немного аккуратней код автора сделал но суть он не меняет), можно запустить онлайн
#include #include
typedef uint64_t u64;
u64 const c_peak = 11241155978086311589ULL; u64 const c_cnt = 13356955260197607378ULL;
u64 peak(u64 nel, int(*less)(u64 i, u64 j)) { if (nel <= 1) return 0; // Note: if nel == 0 there is no answer! if (!less(0, 1)) return 0; if (!less(nel - 1, nel - 2)) return nel - 1;
u64 l = 1, r = nel - 1; while (r - l > 2) { u64 m = l + (r - l) / 2; if (less(m + 1, m)) r = m + 1; else l = m; } if (r - l == 2 && !less(l, l + 1) || r - l <= 1) return l; else return l + 1; }
int less(u64 i, u64 j) { if (i == j) return 0;
if (i < j) { if (j <= c_peak) return 1; if (i >= c_peak) return 0; return (c_peak - i) < (j - c_peak); } else { if (i <= c_peak) return 0; if (j >= c_peak) return 1; return (c_peak - j) < (i - c_peak); } }
u64 peak(u64, int (*)(u64, u64));
int main(int argc, char **argv) { u64 i = peak(c_cnt, less); if (i == c_peak) { printf("CORRECT
"); } else { printf("WRONG
"); } return 0; }