10866.
Тернарный поиск в массиве
Тернарный
поиск принадлежит классу алгоритмов “Разделяй и Властвуй” и
может быть использован для поиска элемента в отсортированном массиве. Он
аналогичен бинарному поиску. Однако в случае тернарного поиска массив делится на
три равные части, после чего определяется в какой из этих частей лежит ключ
(искомый элемент).
Задан отсортированный
массив n целых чисел. Вам
следует ответить на q запросов: содержится
ли заданное число x в
массиве.
Вход. Первая
строка содержит два числа n и q (n,
q ≤ 106). Вторая
строка содержит n целых чисел,
отсортированных по возрастанию. Каждая из следующих q строк содержит значение x.
Числа в массиве не превышают по модулю 109.
Выход. Для каждого значения x выведите в отдельной строке “YES” если x присутствует в массиве и
“NO” иначе.
|
Пример входа 1 |
Пример выхода 1 |
|
6 3 2 4 4 8 11 14 10 4 2 |
NO YES YES |
|
|
|
|
Пример входа 2 |
Пример выхода 2 |
|
8 4 -8 -8 -1 1 3 4 6 8 4 10 -4 -8 |
YES NO NO YES |
РЕШЕНИЕ
тернарный поиск
Анализ алгоритма
В задаче следует найти число в отсортированном массиве. Совершим
это при помощи тернарного поиска.
Пусть ищется элемент x в массиве m на промежутке [start; end]. Делим отрезок на три равные части [start; end], положив
·
mid1 = start + (end – start)
/ 3;
·
mid2 = end – (end – start)
/ 3;
Если x равно m[mid1] или m[mid2], то число x найдено, возвращаем 1. Иначе в
зависимости от следующих условий продолжаем поиск в одном из интервалов:
·
если x < m[mid1], то x лежит на отрезке [start; mid1 – 1].
·
если m[mid1] < x < m[mid2], то x лежит на отрезке [mid1 + 1; mid2 – 1].
·
если x > m[mid2], то x лежит на отрезке [mid2 + 1; end].
Реализация алгоритма
Объявим рабочий массив.
#define MAX 1000001
int m[MAX];
Функция my_ternary_search
возвращает 1, если элемент x присутствует в массиве m[start; end].
int my_ternary_search(int* m, int start, int end, int x)
{
while (start < end)
{
int mid1 = start + (end - start) / 3;
int mid2 =
end - (end - start) / 3;
if (x == m[mid1])
return 1;
if (x == m[mid2])
return 1;
if (x < m[mid1])
end = mid1 - 1;
else if (x < m[mid2])
{
start = mid1 + 1;
end = mid2 - 1;
}
else
start = mid2 + 1;
}
return x == m[start];
}
Основная часть программы. Читаем входные данные.
scanf("%d %d", &n, &q);
for (i = 0; i < n; i++)
scanf("%d", &m[i]);
Последовательно обрабатываем q запросов
при помощи тернарного поиска.
for (i = 0; i < q; i++)
{
scanf("%d", &x);
if
(my_ternary_search(m, 0, n - 1, x))
puts("YES");
else
puts("NO");
}
Java реализация
import java.util.*;
import java.io.*;
public class Main
{
public static int m[];
public static boolean my_ternary_search(int start, int end, int x)
{
while (start < end)
{
int mid1 = start + (end - start) / 3;
int mid2 = end - (end - start) / 3;
if (x == m[mid1]) return true;
if (x == m[mid2]) return true;
if (x < m[mid1])
end = mid1 - 1;
else if (x < m[mid2])
{
start = mid1 + 1;
end = mid2 - 1;
}
else
start = mid2 + 1;
}
return x == m[start];
}
public static void main(String []args)
{
//Scanner con = new Scanner(System.in);
FastScanner con =
new FastScanner(new InputStreamReader(System.in));;
int n = con.nextInt();
int q = con.nextInt();
m = new int [n+1];
for (int i = 0; i < n; i++)
m[i] = con.nextInt();
for (int i = 0; i < q; i++)
{
int x = con.nextInt();
if (my_ternary_search(0, n - 1, x))
System.out.println("YES");
else
System.out.println("NO");
}
//con.close();
}
}
class FastScanner
{
private BufferedReader br;
private StringTokenizer st;
public FastScanner(InputStreamReader reader)
{
br = new BufferedReader(reader);
}
public String next()
{
while (st == null || !st.hasMoreTokens())
{
try
{
st = new StringTokenizer(br.readLine());
} catch (Exception e)
{
e.printStackTrace();
}
}
return st.nextToken();
}
public int nextInt()
{
return Integer.parseInt(next());
}
public double nextDouble()
{
return Double.parseDouble(next());
}
public void close() throws Exception
{
br.close();
}
}