IOM 2020, Блиц — Задача 59

The Blitz-contest of IOM-2020

Условие

Given the following binary search algorithm:

int X, L, R, c;L = 0; R = N;while ( L < R-1 ){c = (L+R) / 2;if ( X < A[c] )R = c;else L = c;}if ( A[L] == X )cout << "A[" << L << "]=" << X << endl;else cout << -1 << endl;\begin{array}{l}\texttt{int X, L, R, c;}\\ \texttt{L = 0; R = N;}\\ \texttt{while ( L < R-1 )}\\ \quad \texttt{\{}\\ \quad \texttt{c = (L+R) / 2;}\\ \quad \texttt{if ( X < A[c] )}\\ \qquad\quad \texttt{R = c;}\\ \quad \texttt{else L = c;}\\ \quad \texttt{\}}\\ \texttt{if ( A[L] == X )}\\ \qquad \texttt{cout << "A[" << L << "]=" << X << endl;}\\ \texttt{else cout << -1 << endl;}\end{array}

How many comparisons will be made if we are looking for an element that is not in the array. Sorted array length NN is 10.

Отговори

Решение

Внимание: Непълно решение

The source contains only the answer key, no worked solution.

Оригинал в Архива: iom-2020-blitz-tasks.pdf · официални решения: iom-2020-blitz-answers.pdf