Как создать алгоритм поиска с временем выполнения части массива в C

Question

Здравствуйте, у меня возникла проблема с вопросом, который я пытаюсь решить, и я буду рад, если кто-нибудь поможет мне разобраться. Я получаю в функции следующие значения: массив, размер массива (s_arr) и число (например, x), которое находится внутри одного из элементов. Массив частично отсортирован (при условии, что у нас есть n отсортированных чисел), а остальная часть массива инициализирована с нулем (1,2,3,…, 19,20,0,0,0, 0,0) Алгоритм, который мне нужно создать, - это найти индекс (при условии, что он существует) числа (x) во время выполнения (сложность по времени) log (n) (основание журнала - 2…) , Я пытался найти некоторые алгоритмы поиска, но все, что я нашел, это двоичная сортировка, но время выполнения двоичного файла будет равно размеру всего массива (я получу время выполнения log (s_arr)). А вот код, который я написал для двоичного кода.

int SearchNumber(int* arr, int s_arr, int x)
{
    int middle = 0, ptrLeft = 0, ptrRight = m;
    int flag = 0;
    while ((ptrLeft <= ptrRight) && !flag)
    {
        middle = (ptrLeft + ptrRight) / 2;
        if (V[middle] == x)
        {
            flag = 1;
            break;
        }
        else
        {
            if (V[middle] == 0  || V[middle] > x)
                ptrRight = middle - 1;
            else
                ptrLeft = middle + 1;
        }
    }
    if (flag == 1)
        return middle;
    return 0;