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

The Blitz-contest of IOM-2020

Условие

int binary_search(vector<int> vec, int value, int n){sort(vec.begin(),vec.end());int l = 0, r = n – 1while (l <= r){int mid = (l + r) / 2;if (vec[mid] <= l)l = mid;elser = mid;}return l;}\begin{array}{l}\texttt{int binary\_search(vector<int> vec, int value, int n)\{}\\ \quad \texttt{sort(vec.begin(),vec.end());}\\ \quad \texttt{int l = 0, r = n – 1}\\ \quad \texttt{while (l <= r)\{}\\ \qquad \texttt{int mid = (l + r) / 2;}\\ \qquad \texttt{if (vec[mid] <= l)}\\ \qquad\quad \texttt{l = mid;}\\ \qquad \texttt{else}\\ \qquad\quad \texttt{r = mid;}\\ \quad \texttt{\}}\\ \quad \texttt{return l;}\\ \texttt{\}}\end{array}

Determine the time complexity of the function above

  • O(N)O(N)
  • O(logN)O(logN)
  • O(NlogN)O(NlogN)
  • O(Nlog2N)O(Nlog^2N)
  • O(∞)O(\infty)

Отговори

Решение

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

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

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