Бинарный поиск (30 октября 2013)

  1. Поиск по массиву [код]
    1. Задача: содержится ли число в массиве.
    2. Реализация. Отрезки vs полуинтервалы.
    3. Задача: найти количество чисел со значением от l до r. Нужно писать не два, а один двоичный поиск.
    4. Задача: найти количество чисел равных x, стоящих в позициях от L до R также решается двоичным поиском
  2. Вещественный бинпоиск [код]
    1. Поиск корня функции, реализация: while (r-l>eps)
    2. Реализация с циклом for(k,60) вместо while (r-l>eps)
  3. Бинпоиск по ответу, задачи
    1. Not read Разрезать доски на n одинаковых кусков максимальной длины (плюс обрубки)
    2. Найти точку сбора тараканов [код]
    3. Вписать окружность максимального радиуса в невыпуклый многоугольник
  4. Троичный поиск
    1. Нахождение локального минимума/максимума. Реализация через a=(2l+r)/3, b=(l+2r)/3
    2. Для выпуклых функций это тоже самое, что бинарный поиск по производной
    3. Для невыпуклых функций мы найдем какой-то минимум.
    4. Реализация через l,m,r
    5. Реализация через золотое сечение
    6. Более общий метод: разбить на куски, на каждом запустить троичный поиск
    7. Задача: описать вокруг выпуклого многоугольника прямоугольник минимальной площади
    8. Вложенные троичные поиски
      1. Вписать круг максимального радиуса в заданный выпуклый многоугольник за O(Nlog2M)
      2. Not read Минимизировать периметр треугольника. A фиксирована, B и C лежат на заданных окряжностях.
  5. Not read Сортировка деревом отрезков?