Задачи и упражнения

1. Дан отсортированный массив А. Найдите, сколько раз число x встречается в этом массиве.
2. Дано вещественное положительное число x. Найдите квадратаный, кубический и $$n$$ степени корень этого числа.
3. Дан отсортированный массив А все элементы которого различны. Найти такой индекс $$i$$, что $$a[i] = i$$ (такой элемент называется неподвижной точкой)
4. С помощью арифметических операций $$+, -, *, /, \sqrt{ }$$ найти значение $$\log_2 x$$ для заданного положительного числа $$x$$
5. Дан массив, элементы которого сначала убывают, а потом возрастают. Найти минимум в массиве.
6. Дан отсортированный массив все элементы которого различны. Массив был сдвинут на $$k$$ позиций вправо. Найти минимальный элемент, а так же $$k$$.
7. Дан отсортированный массив все элементы которого различны. Массив был сдвинут на $$k$$ позиций вправо. Определить содержит ли данный массив заданное число $$x$$. (ИТМО)
8. Даны два отсортированных массива длины $$n$$ и $$m$$. Найти $$k$$ элемент в их отсортированном объединении.
9. Дан массив элементы которого сначала возрастают, а затем убывают. Определить содержит ли данный массив заданное число $$x$$. (ИТМО)
10. Дан отсортированный массив А все элементы которого различны. Определить содержит ли данный массив заданное число $$x$$ используя лишь операции сложения, вычитания, а так же константное количество памяти.
11. Дан массив содержащий $$n$$ целых чисел. Найти непрерывную подпоследовательность длины как минимум $$k$$ с наибольшим средним значением.
12. Найти наибольшую подстроку являющуюся полиндромом за время $$\mathcal{O}(n\log n)$$ (задача может быть решена за линейное время).
13. Два отсортированных по возрастанию массива записаны один в конец другого. Требуется максимально быстро найти элемент в таком массиве.
14. Массив образован путем циклического сдвига массива, образованного приписыванием отсортированного по убыванию массива в конец отсортированного по возрастанию. Требуется максимально быстро найти элемент в таком массиве.
15. Дан массив, элементы которого сначала возрастают, а потом убывают. Найти максимум в массиве (элемент начиная с которого элементы убывают).
16. Дан отсортированный массив размера $$n$$. Найти минимальный пропущенный элемент.

17. В последовательности записаны целые числа от 1 до N в произвольном порядке, но одно из чисел пропущено (остальные встречаются ровно по одному разу). N заранее неизвестно. Определить пропущенное число.

18. В последовательности записаны целые числа. Одно из чисел встречается ровно один раз, остальные — по два раза. Найти число, которое встречается один раз.

19. В последовательности записаны целые числа. Число X встречается один или два раза, остальные числа — по три раза. Найти число X. Для простоты считаем, что числа неотрицательные.

20. В последовательности записаны целые числа. Число X встречается 1,2 или 3 раза, остальные числа — по 4 раза. Найти число X.

21. В последовательности записаны целые числа, больше половины из которых равны одному и тому же числу X. За один просмотр последовательности найти это число.

22. В последовательности записаны целые неотрицательные числа, меньшие M, причём известно, что каждое число встречается не более одного раза. Найти наименьшее число, которое в этой последовательности не встречается.

23. В последовательности записано M+1 целое неотрицательное число, все числа меньше M. Найти какое-нибудь число, которое встречается хотя бы дважды.

24. Мажорирующим элементом в массиве A[1..N] будем называть эле-мент, встречающийся в массиве более N/2 раз. Легко заметить, что в массиве может быть не более одного мажорирующего элемента. Например, массив

    3, 3, 4, 2, 4, 4, 2, 4, 4

    имеет мажорирующий элемент 4, тогда как в массиве

    3, 3, 4, 2, 4, 4, 2, 4

    мажорирующего элемента нет. Необходимо определить, есть ли в массиве мажорирующий элемент, и если есть, то какой.

25. Задано N наборов монет из различных стран. Наборы упорядочены по невозpастанию массы монет. В i-ом наборе a_i монет. Необходимо
    за минимальное число взвешиваний на чашечных весах определить
    к-тую по массе монету среди всех монет.

26. Вводится последовательность из n натуральных чисел.Необходимо определить наименьшее натуральное число, отсутствующее в последовательности.

27. На длинной перфоленте записаны N попарно различных положительных целых чисел. Ваша ЭВМ может перематывать ленту на начало и
    считывать числа одно за другим. Внутренняя память машины может
    хранить только несколько целых чисел. Требуется найти наименьшее
    положительное целое число,которого нет на ленте. Опишите алгоритм,который сделает это за небольшое количество перемоток ленты.

http://algorithmsandme.in/2015/04/binary-search-algorithm-and-related-problems/\**

https://habrahabr.ru/post/243819/

http://algorithmsandme.in/tag/binary-search/

http://www.geeksforgeeks.org/find-the-point-where-a-function-becomes-negative/

Given A a sorted array find out how many times does x occur in A. (Дан отсортированный массив А. Найдите, сколько раз число x встречается в этом массиве.)

Given a real number x, find out its cubic root. (Дано вещественное число x. Найдите кубический корень этого числа.)

Given A a sorted array with distinct numbers, find out an i such that A[i] == i.

Given the +,-,*,/,sqrt operations and a real number x find an algorithm to get log_2_x.

Given an array of distinct numbers A such that A[0] > A[1] and A[n-1]> A[n-2] find out a local minimum (find out an i such that A[i-1] > A[i] < A[i + 1]).

Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out k.

Let A be a sorted array with distinct elements. A is rotated k positions to the right (k is unknown). Find out if A contains a number x.

Given two sorted arrays of length n and m, find out the kth element of their sorted union.

Given A, an array comprised of an increasing sequence of numbers followed immediately by a decreasing one. Determine if a given number x is in the array.

Given an array of N distinct int values in ascending order, determine whether a given integer is in the array. You may use only additions and subtractions and a constant amount of extra memory.

Player A chooses a secret number n. Player B can guess a number x and A replies how does x compare to n (equal, larger, smaller). What's an efficient strategy for B to guess n.

Problem: Given a list of N integers, find the consecutive subsequence of at least length K with the maximum average.

Find the largest palindromic substring of a string in O(N log N) (this can actually be done in linear time!).