Рубрики

Алгоритмы | Поиск | Вопрос 4

Рассмотрим следующую программу на C, которая пытается найти элемент x в массиве Y [] с помощью бинарного поиска. Программа ошибочная. (GATE CS 2008)

1.   f(int Y[10], int x) {

2.     int i, j, k;

3.     i = 0; j = 9;

4.     do {

5.             k =  (i + j) /2;

6.             if( Y[k] < x)  i = k; else j = k;

7.         } while(Y[k] != x && i < j);

8.     if(Y[k] == x) printf ("x is in the array ") ;

9.     else printf (" x is not in the array ") ;

10. }

На каком из следующих содержаний Y и x происходит сбой программы?
(A) Y равен [1 2 3 4 5 6 7 8 9 10] и x <10
(B) Y равен [1 3 5 7 9 11 13 15 17 19] и x <1
(C) Y представляет собой [2 2 2 2 2 2 2 2 2 2] и x> 2
(D) Y равен [2 4 6 8 10 12 14 16 18 20] и 2 <x <20 и x четный

Ответ: (с)
Объяснение: Приведенная выше программа не работает в тех случаях, когда искомый элемент является последним элементом Y [] или больше последнего элемента (или максимального элемента) в Y []. Для таких случаев программа идет в бесконечном цикле, потому что мне присваивается значение как k на всех итерациях, и я никогда не становлюсь равным или превышающим j. Так что пока условие никогда не становится ложным.
Тест на этот вопрос

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

Алгоритмы | Поиск | Вопрос 4

0.00 (0%) 0 votes