Целочисленный двоичный поиск — различия между версиями
Rukin (обсуждение | вклад) |
|||
| Строка 3: | Строка 3: | ||
== Формулировка задачи == | == Формулировка задачи == | ||
Пусть нам дана монотонная функция, значения которой целые числа. Нам необходимо найти место, где функция будет равна заданному значению. | Пусть нам дана монотонная функция, значения которой целые числа. Нам необходимо найти место, где функция будет равна заданному значению. | ||
| + | |||
| + | == Выбор границы == | ||
| + | Нам должны быть заданы границы, на которых мы ищем индекс заданного значения <b>х</b>. | ||
| + | |||
| + | == Правосторонний/левосторонний целочисленный двоичный поиск == | ||
| + | Когда мы ищем правосторонним бин. поиском, то он возвращает индекс самого правого вхождения заданного значения <b>х</b>.<br> | ||
| + | Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения <b>х</b>.<br> | ||
| + | Это разделение помогает находить количество подряд идущих равных значений.<br> | ||
| + | <b><i>Например:</i></b> <br> | ||
| + | Задан отсортированный массив [1, 2, 2, 2, 2, 3, 5, 8, 9, 11] <br> | ||
| + | Правосторонний поиск двойки выдаст в результате 5, в то время как левосторонний выдаст 2. <br> | ||
| + | От сюда следует, что количество подряд идущих двоек равно длине отрезка [2;5] = 4. <br> | ||
| + | |||
[[Файл:cheme.jpg]] | [[Файл:cheme.jpg]] | ||
Версия 19:50, 24 мая 2012
Целочисленный двоичный поиск - алгоритм поиска аргумента для заданного значения монотонной целочисленной функции.
Формулировка задачи
Пусть нам дана монотонная функция, значения которой целые числа. Нам необходимо найти место, где функция будет равна заданному значению.
Выбор границы
Нам должны быть заданы границы, на которых мы ищем индекс заданного значения х.
Правосторонний/левосторонний целочисленный двоичный поиск
Когда мы ищем правосторонним бин. поиском, то он возвращает индекс самого правого вхождения заданного значения х.
Когда же поиск левосторонний, возвращается индекс самого левого вхождения заданного значения х.
Это разделение помогает находить количество подряд идущих равных значений.
Например:
Задан отсортированный массив [1, 2, 2, 2, 2, 3, 5, 8, 9, 11]
Правосторонний поиск двойки выдаст в результате 5, в то время как левосторонний выдаст 2.
От сюда следует, что количество подряд идущих двоек равно длине отрезка [2;5] = 4.
