Задача 1

Используя бинарный поиск, находим индекс первого вхождения $$x$$ в массив (левый бин. поиск). Пусть индекс первого вхождения будет $$i$$. Далее, бинарным поиском находим индекс последнего вхождения x в массив (правый бин. поиск). Пусть индекс последнего вхождения будет $$j$$. Возвращаем ответ: $$j-i+1$$.

Задача 2

Для решения этой задачи используем бинарный поиск. Сначала задаём погрешность, с которой мы ищем корень. Пусть $$er=0.00001$$. Далее:

1. Определяем $$start = 0$$, $$end=n$$;
2. Вычисляем $$mid=start+(end-start)/2$$;
3. Проверяем, если $$|n-mid^3|<er$$, то $$mid$$ это наш ответ;
4. Иначе если $$mid^3>n$$, то присваиваем $$end=mid$$ и повторяем все действия с п.2;
5. Иначе присваиваем $$start=mid$$ и повторяем все действия с п.2.

Для корней других степеней задача решается аналогично.

Задача 3

Используем бинарный поиск. $$n$$ - количество элементов в массиве

1. Определяем $$start=0$$, $$end=n-1$$;
2. Вычисляем $$mid=start+(end-start)/2$$;
3. Если $$A[mid]==mid$$, то $$mid$$ будет ответом;
4. Иначе, если $$mid>A[mid]$$, то $$start=mid+1$$ и повторяем все действия, начиная с п.2;
5. Иначе $$end=mid-1$$ и повторяем все действия, начиная с п.2.

Задача 4

Решается аналогично задаче 2.

Задача 5

Используем бинарный поиск.

1. Определяем $$start=0$$, $$end=n-1$$;
2. Вычисляем $$mid=start+(end-start)/2$$;
3. Если $$A[mid-1]>A[mid]$$ and $$A[mid+1]>A[mid]$$, то $$A[mid]$$ и есть искомый минимум;
4. Иначе, если $$A[mid]>A[mid - 1]$$, тогда присваиваем $$end=mid-1$$ и выполняем пункты, начиная с п.2;
5. Иначе $$start = mid + 1$$ и выполняем пункты, начиная с п.2;

Задача 6

Назовём эту точку pivot. Тогда:

int findPivot(int arr[], int low, int high)
{
   // base cases
   if (high < low)  return -1;
   if (high == low) return low;

   int mid = low + (high - low)/2;
   if (mid < high && arr[mid] < arr[mid-1])
      return mid;
   if (mid > low && arr[mid] > arr[mid+1])
      return mid+1;
   if (arr[low] >= arr[mid])
       return findPivot(arr, low, mid-1);
   return findPivot(arr, mid + 1, high);
}

Пусть после выполнения этого метода мы получили индекс $$i$$. Тогда минимумом в массиве будет $$arr[i]$$, а $$k = i$$.

Задача 7

Используя метод из задачи 6 найти $$pivot$$ (только теперь это должен быть наибольший элемент в массиве). Этим пивотом наш массив разбивается на два отсортированных подмассива. Чтобы найти необходимый элемент $$x$$ вызываем бинарный поиск для того подмассива, для которого выполняется условие $$arr[low] <= x <= arr[high]$$.

Задача 8

Одним из способов решения этой задачи является слияние обоих массивов в один отсортированный массив, а затем возврат k-ого элемента объединённого массива.

Но нужно ли нам объединять полностью эти два массива? Или мы можем отбросить какую-то их часть?

Найдём $$i=min(sizeA,k/2)$$ для первого массива и $$j=min(sizeB,k/2)$$ для второго массива. Теперь если $$A[i]>B[j]$$, то искомый элемент будет среди элементов с индексом больше чем $$j$$ из второго массива и меньше чем $$i$$ из первого массива.

Иначе, если $$A[i]<B[j]$$, то искомый элемент будет среди элементов с индексом меньше чем $$j$$ из второго массива и больше чем $$i$$ из первого массива.

Также будут некоторые простые случаи, которые надо рассмотреть отдельно.

int findKthSmallestElement(int a[], int b[], int sizeA, int sizeB, int k)
{
  /* to maintain uniformity, we will assume that 
     size_a is smaller than size_b
      else we will swap array in call*/
  if(sizeA > sizeB)
    return findKthSmallestElement(b, a, sizeB, sizeA, k);
  /* Now case when size of smaller array is 0 
     i.e there is no elemt in one array*/
  if(sizeA == 0 && sizeB >0)
    return b[k-1]; // due to zero based index

  /* case where K ==1 that means we have hit limit */
  if(k ==1)
    return min(a[0], b[0]);

  /* Now the divide and conquer part */
  int i =  min(sizeA, k/2) ; // K should be less than the size of array  
  int j =  min(sizeB, k/2) ; // K should be less than the size of array  

  if(a[i-1] > b[j-1])
    // Now we need to find only K-j th element
    return findKthSmallestElement(a, b+j, sizeA, (sizeB-j), k-j);
  else
    return findKthSmallestElement(a+i, b, (sizeA-i), sizeB, k-i);
}

Задача 9

Аналогично задаче 5 находим индекс максимального элемента в массиве. Пусть число элементов в массиве $$n$$, а индекс максимального - $$mid$$. Далее, если $$A[0] \le x \le A[mid]$$, то осуществляем бинарный поиск по этой части массива, иначе - бинарно ищем наше число от $$A[mid+1]$$ до $$A[n-1]$$.

Задача 13

Запустить бинарный или тернарный поиск сразу мы не можем в силу того, что общий массив не отсортирован, поэтому можно за O(n) найти ту самую границу, а затем запустить бинарный поиск от двух подмассивов. Сложность получится O(n + 2log(n)) = O(n).

Задача 14

После циклического сдвига мы получим массив a[0...n-1], образованный из трех частей: отсортированных по возрастанию-убыванию-возрастанию или по убыванию-возрастанию-убыванию. С помощью двоичного поиска найдем индексы максимального и минимального элементов массива, заменив условие в if на a[m] > a[m - 1] (ответ будет записан в l) или на a[m] > a[m + 1] (ответ будет записан в r) соответственно.

Фактически, при поиске индексов минимума и максимума мы проверяем, возрастает или убывает массив на промежутке [ m - 1; m ], а затем, в зависимости от того, что мы ищем, мы либо поднимаемся, либо опускаемся по этому промежутку возрастания (убывания). Однако при таком решении могут быть неправильно найдены значения минимума или максимума. Рассмотрим случаи, когда они будут неправильно найдены. Определить, какого вида наш массив возможно, сравнив первые два элемента массива.

Рассмотрим отдельно ситуацию, если наш массив вида возрастание-убывание-возрастание. В таком случае может быть неправильно найдено значение максимума, если последний промежуток возрастания занимает больше половины массива (мы будем подниматься по последнему промежутку возрастания вплоть до конца массива и за максимум будет принят последний элемент массива, что не всегда верно). Тогда, если последний элемент массива меньше первого, нужно еще раз запустить поиск максимума, но уже на промежутке от 0 до min, потому что истинный максимум будет находиться в первой точке экстремума, которую мы таким образом и найдем.

В случае же убывание-возрастание-убывание может быть, что будет неправильно найден минимум. Найдем правильный минимум аналогично поиску максимума в предыдущем абзаце.

Затем, в зависимости от типа нашего массива, запустим бинарный поиск три раза на каждом промежутке.

Время выполнения данного алгоритма — O(6log n)=O(log n).

Задача 15

Находим бинарным поиском середину. Если текущий элемент больше предыдущего{, то если текущий еще и больше следующего,[ то нашли], иначе [идем вправо], }иначе {идем влево}.

//псевдокод с использованием оператора case
if (a[i] > a[i-1]){
    switch ((a[i]-a[i+1])/abs(a[i]-a[i+1])){
        -1:идем вправо; break;
         1:нашли; break;
    }
}else{
    идем влево;
}

Задача 16

Находим бинарным поиском середину. Если индекс соответствует значению, значит всё нормально, идем искать в правую часть. Если индекс не соответствует значению, идем в левую. Поиск продолжается до тех пор, пока не найден подмассив длиной 1.

Задача 17

Так как один элемент пропущен, то количество элементов $$K = N - 1$$

Таким образом, если вы знакомы с методом Гаусса поиска суммы чисел от 1 до N, то наша сумма должна быть равна $$(K+1) * (K+2)/2$$. Теперь пройдем по всему массиву и посчитаем непосредственно количество элементов K и их сумму S.

Чтобы найти отсутствующее число нам достаточно лишь посчитать $$(К+2) * (K+1)/2 - S$$

P.S. Аккуратнее с K+1 и K+2 :)

Задача 18

Найдем XOR всех чисел — он и будет ответом. В самом деле, если какой-то бит в искомом числе равен нулю, то во всей последовательности он будет равен 1 в чётном числе элементов, и его значение в XOR равно нулю. В противном случае, аналогично, его значение в XOR равно 1. Или, проще говоря, одинаковые элементы при суммировании взаимоуничтожатся.

Задача 19

Поступим аналогично предыдущей задаче: переведём каждое из чисел в троичную систему: $$b=b[0]+3b[1]+32b[2]+…$$ Для каждого разряда найдём сумму его значений по модулю 3 (обозначим суммы $$s[0],s[1],s[2],...$$). Кроме того, посчитаем сами числа.

Если чисел в последовательности было $$3k+1$$, то X встретился один раз, и его значение равно $$s[0]+3s[1]+32s[2]+…$$ Если же чисел было 3\k+2, то в наборе s[i] единицы придётся заменить на двойки и наоборот: $$$$$$x[i]=(3-s[i])%3$$ и $$X=x[0]+3x[1]+32x[2]+…$$

Задача 20

Предыдущий подход здесь уже не сработает: если мы возьмём систему счисления с основанием 4, и найдём поразрядные суммы, то для случаев, когда X встретился один или три раза, всё будет хорошо. Но если X встретился дважды, мы уже не сможем узнать, была ли очередная цифра равна 0 или 2 — значение суммы si для этого разряда в обоих случаях будет равно нулю. Что делать?

На самом деле, в прошлый раз я вас обманул. Совершенно незачем возиться с троичной системой — достаточно было посчитать сумму битов в каждом двоичном разряде, и если она делилась на 3, то в числе X соответствующий бит равнялся нулю. Если нет — то единице.

В этой задаче делаем точно так же, но проверяем делимость на 4. Например, эти задачи можно решить так:

static int FindNotThree(IEnumerable<int> seq) {
            int a=0,b=0;
            foreach(int c in seq) {
                a^=~b&c;
                b^=~a&c;
            }
            return a|b;
        }
static int FindNotFour(IEnumerable<int> seq) {
            int a=0,b=0;
            foreach(int c in seq) {
                a^=b&c;
                b^=c;
            }
            return a|b;
        }

Задача 21

Заметим, что если мы вычеркнем из последовательности два различных числа, то условие задачи останется верным. Поэтому мы можем вычёркивать пары различных чисел до тех пор, пока все элементы не станут равными одному и тому же числу. Это число и будет X.

Чтобы реализовать этот метод, заведём ячейку, в которой будет храниться какой-то элемент последовательности, и счётчик — сколько копий этого элемента у нас просмотрено и пока не вычеркнуто.

Когда мы читаем очередной элемент, у нас есть три варианта:

— Счётчик равен нулю. Кладём прочитанный элемент в ячейку, увеличиваем счётчик на 1.

— Элемент равен значению ячейки. Увеличиваем счётчик на 1.

— Элемент не равен значению ячейки. Уменьшаем счётчик на 1.

После того, как мы просмотрим всю последовательность, в ячейке окажется искомое число.

К сожалению, обобщить это решение на случай, когда число X встречается больше, чем в 1/k случаев (k известно), не удаётся. Мы можем так же завести k-1 ячейку со счётчиком, удалять за один раз по k различных элементов, получим в конце k-1 кандидата на роль X, но опознать его нам не удастся — даже значение счётчика у него будет не самым большим. Зато если нам разрешат сделать второй проход, мы можем посчитать, сколько раз каждый из кандидатов встретился в последовательности, и выдать гарантированно самого частого.

У исходной задачи есть ещё одно решение. Для каждого бита считаем, сколько раз он равнялся 0, а сколько — 1, и выдаём более частое значение. Возможно, его удастся обобщить на случай, когда X встречается больше, чем в 1/3 случаев — посчитаем статистику для каждой пары битов… вдруг поможет?

Задача 22 и 23

Решения практически одинаковы. Делим диапазон 0..M-1 на две или более частей. Для каждой части подсчитываем, сколько чисел в неё попало. В 22 задаче оставляем самый ранний поддиапазон, в который попало меньше чисел, чем его длина, в 23 — любой из поддиапазонов, в который попало больше чисел, чем его длина. Процесс повторяем, пока не останется диапазон из одного числа. Оно и будет ответом.

Задача 24

Метод 1

Отсортируем исходный массив по неубыванию, а затем просмотрим
его, подсчитывая число идущих подряд одинаковых элементов.

Метод 2

Мы заведем стек и будем добавлять и извлекать из стека элементы по следующему правилу:

1) На первом шаге помещаем в стек A[0] .

2) На i-ом шаге, i=1, ..., N повторяем следующие действия:

Если стек пуст,

то помещаем в него A[i]

иначе

       если элемент A\[i\] совпадает с элементом

на верхушке стека

       то добавляем A\[i\] в стек


       иначе удаляем элемент с верхушки стека.

Если стек не пуст, то в нем находятся лишь совпадающие элементы. Если у нас в последовательности есть мажорирующий элемент,
то он и останется в стеке после N-го шага (мажорирующие элементы
встречаются в последовательности более N/2 раз, и не могут при
выполнении N шагов алгоритма "сократиться" со всеми остальными
немажорирующими элементами).
Для проверки (в случае непустого стека после выполнения N-го
шага) является ли элемент в стеке мажорирующим (если в стеке более одного элемента, то они все совпадают), мы просматриваем массив еще один раз и подсчитываем, сколько раз встречается в
массиве элемент из стека. Если это число больше N/2, то этот элемент мажорирующий, иначе - мажорирующего элемента в последовательности нет.

Задача 25

Очевидным решением задачи является создание общего упорядоченного массива, содержащего элементы всех массивов, и нахождение в нем k-того по величине элемента.

Однако можно существенно сократить трудоемкость.Пусть для каждого из наборов i определены начальный Ni и конечный Ki индексы. Определим индексы средних элементов Si=(Ni+Ki)
div 2. ВычислимS=S1+S2+... +SN.

Возможны три ситуации:

1. S > k
   Очевидно, что если найти минимальный элемент среди средних
   элементов (пусть он в наборе j), то ни один из элементов с индексами Sj,...,Kj заведомо не является решением. Поэтому можно пересчитать Kj=Sj-1 (если Kj>Nj).

2. S < k
   Очевидно, что если найти максимальный элемент среди средних
   элементов (пусть он в наборе t), то ни один из элементов с индексами Nt,...,St заведомо не является решением. Поэтому можно пе
   ресчитать Nt=St+1 (если Kt>Nt).

3. S = k
   Очевидно, что в этом случае можно пересчитать Kj=Sj и
   Nt=St+1.
   Процесс заканчивается, когда начальный N[i] и конечный K[i]
   индексы удовлетворяют условию K[i]<=N[i] для каждого i. При этом
   меньший из элементов с индексами K[i] и будет искомым (если K[i]=0, то этот элемент рассматривать не нужно).

Задача 26

Очевидно, что при вводе n натуральных чисел по крайней мере одно число из интервала [1,n+1] отсутствует.

Поэтому идея решения состоит в том, что отводится массив из n чисел, в котором элемент с индексом i регистрирует, пришло ли число со значением i. После регистрации всех элементов последовательности осталось только проверить, какое минимальное число не зарегистрировано. (В качестве признака регистрации числа i можно заносить в i-ый элемент массива 1. Первоначально все числа не зарегистрированы - все элементы массива равны 0).

Если все числа от 1 до n зарегистрированы, то минимальное отсутствующее натуральное - n+1.

Задача 27

Очевидно, что при вводе n натуральных чисел по крайней мере
одно число из интервала [1,n+1] отсутствует.

Определим начало a и конец b некоторого интервала индексов,
который нас интересует. Возможно ли за один просмотр ленты установить, все ли числа из интервала [a,b] присутствуют на ленте? Учитывая факт, что записанные числа различны, можно определить,
сколько чисел, записанных на ленте, попадают в интересующий нас
интервал. С другой стороны, нетрудно определить количество натуральных чисел на интервале [a,b] - это (b-a+1).
Поэтому алгоритм состоит в следующем.
Определим значения начала и конца интересующего нас интервала. Очевидно, что вначале они равны 1 и N+1 соответственно.
Пусть на некотором шаге значения начала и конца интересующего
нас интервала равны f и l соответственно. Определим индекс среднего элемента интервала m=(f+l) div 2.

Определяем теперь количество элементов k на ленте, лежащих в
интервале [f,m].

Возможны следующие ситуации:

1. Количество элементов k<m-f+1 .

В этом случае нас не интересует интервал от m до l, так как
на интервале [f,m] хотя бы одно число отсутствует. Поэтому интересующим нас интервалом можно считать [f,m]. Поэтому полагаем
l:=m.

1. Количество элементов k=m-f+1. В этом случае нас не интересует интервал от f до m, так как на интервале [f,m] все натуральные присутствуют. Поэтому интересующим нас интервалом можно считать [m+1,l]. Поэтому полагаем l:=m+1.

Процесс оканчивается, когда f=l.