Ну як там буде 4 виклики? Викликів не більше 2, навіть якщо не знайдеться. Власне, не знайдеться чи знайдеться на останньому кроці - складність однакова.

Нехай, але у мене немає такого коду. Очі розуйте. У мене

if(умова1) {
    return a || b;
} else {
    return c || d;
}

У вас матриця дуже щільно близькими значеннями заповнюється, в результаті у вас практично в першиму ж рядку пошук знаходить потрібне значення і складність падає до O(log(N)). Поставте

const int num_max = 10'000'000;

чи біля того, щоб трохи розрядити числа.

Це, - слушне зауваження. Дiйсно, якщо пощукове значення мiстится десь на початку матрицi, то змагання не рiвне. Я вирiшив дiапазон пошуку почати з середини, а закiнчити на одну чверту пicля.

const int num_min = num_max / 2;
const int v_size = 1000; // 10
const int search_number = 1000000; // 5

отак iнiцiалiзуєцця вектор значеннь для пошуку:

std::vector<std::vector<int>>
    matrix (
        make_matrix(0, num_max, v_size) // початок з нуля
    );
    std::vector<int> vtargets = make_source_vector(
        num_min, num_max + num_min / 2, search_number
    );
    // оскiльки num_min = num_max / 2 то перша половина матрицi не бере участь у пошуцi
    // а змiщення верхнього рубежу гарантуе присутнicть чвертi невдалих спроб

кiлькicть повторiв вплива тiльки на точнiсть, але я iї збiльшив до мiльйону. Але це не дуже вплинуло. Треба ще щось придумати.
Навiть

const int num_min = 3 * num_max / 4; // num_max / 2

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

Я спробував. Тобто уся 2d матриця заповнена рядом вiд 0 до dim*dim. Шукав даннi середнього рядку.

std::vector<std::vector<int>>
    matrix(v_size);
    size_t num(0);

    for(auto &subvec:matrix) {
        for(size_t i = 0; i < v_size; ++i) {
            subvec.push_back(num++);
        }
    }
    std::vector<int> vtargets = matrix[v_size / 2]; // посерединi
    std::cout << "\nfind_in_matrix\n";
    {
        simple_timer st;
        for(auto target : vtargets) {
            bool res = find_in_matrix(matrix, target);
            // cout << res << '\n';
        }
    }
    std::cout << "\nSolution\n";
    Solution sol;
    {
        simple_timer st;
        for(auto target : vtargets) {
            bool res = sol.searchMatrix(matrix, target);
            // cout << res << '\n';
        }
    }

Але швидкість майже у 10-теро менше нiж у мойого. Я думаю, що те що мойому доводится мати N/2 невдалих спроб, вiн легко це долає за рахунок швидкої перевiрки дiапазону, у той час як вашому треба зробити по 2 рекурсiї. Хех... Здається, це досить непросте завдання, знайти алгоритм заповнення такої матрицi данними, що зроблять ваш алгоритм швидкiшим.

У-у-пс... Дiйсно. Я не перключився у релiз. Тепер, набагато краще! Але текучий тест трохи все ж таки трохи повiльнiший за мiй. А попереднiй - де початок набору цiлей з 3/4 num_max - у 5 разiв.

Саме це я й маю на увазi, коли говорю про те, що знайти алгоритм пошуку послiдовностi, що маматиме шукатися у у матрицi, росподiлення у якiй теж нетривiальне (сопряжено до першої, сформульованої задачи), це досить непросто, принаймнi, для мене. Але без цього, неможливо визачити межi застосовністi вашого алгоритму. Поки що схоже на те, що у разi ровномiрного розподiлення у пошуковому iнтервалi, та матрицi стосовно заданого iнтервалу значень, ваш алгоритм програє. Доречи, сам алгоритм заповнення матрицi, згiдно обмежень задачи цього топику - досить теж задача не проста у загальнiй постановцi. Я вже писав, що якщо даннi у матрицi сортованi, то то є часний випадок, але для нього я (спочатку не розiбравши докладно), написав бiнарний пошук у бiнарному пошуцi. Це значно швидше, нiж спочатку перебирати, а потiм бiнарити...
С iншого боку, обмеження задачi досить неприроднi i не мають загального сенсу. Тож мiркувати над цим, це суто академiчне питання. Може воно й не вартe часу. Ось чому я не люблю задачi сформульованi математиками якi не цiкавляться питаннями здорового глузду. Я вже про це кеазав. Але де шукати iньшi я теж не знаю. В цiлому хочу подякувати Teg Miles, за топик, що викликав нашi роздуми i вам та iншiм учасникам за участь.

га ? я аж чайом подавився. В чому треба допомога ?

O( sum{ c*log(N/k) } ) так й залишиться O( log(N) ).
Тільки продукт добуток O( product{ c*log(N/k) } ) трохи більший ніж O( log(N) ).
А якщо треба { код | алґоритм }, то це почекає до вихідних коли появляться сили.

Тоді log(N/2^k) = log(N) - k*log(2), і оцінка буде .. а ні, не буде, десь дужка пропала, не знаю як це читати.