Рубрики

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 65

GATE

Рассмотрим функцию C, приведенную ниже. Предположим, что массив listA содержит n (> 0) элементов, отсортированных по возрастанию.

int ProcessArray(int *listA, int x, int n)

{

    int i, j, k;

    i = 0;

    j = n-1;

    do

    {

        k = (i+j)/2;

        if (x <= listA[k])

            j = k-1;

        if (listA[k] <= x)

            i = k+1;

    }

    while (i <= j);

    if (listA[k] == x)

        return(k);

    else

        return -1;

}

Какое из следующих утверждений о функции ProcessArray является ПРАВИЛЬНЫМ?
(A) Он попадет в бесконечный цикл, когда x отсутствует в listA.
(B) Это реализация бинарного поиска.
(C) Он всегда найдет максимальный элемент в listA.
(D) Он вернет -1, даже если x присутствует в listA.

Ответ: (Б)
Объяснение:

The function is iterative implementation of Binary Search.  

k keeps track of current middle element.

i and j keep track of left and right corners
of current subarray

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2014- (Set-3) | Вопрос 65

0.00 (0%) 0 votes