HM248 有序二分

来源： 第 248 集 常用查找算法-binary_search

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

binary_search 判断指定元素是否存在，返回值是 bool：存在为真，不存在为假。这和 find / find_if 不同——那两个返回的是迭代器，这个只反馈有没有，不能用来打印“找到的那个元素”。

三个参数：区间起点、区间终点、要查的值。拼写是 binary 下划线 search。头文件 algorithm。

它底层是二分查找，速度很快，但**必须在有序序列上使用**。无序时结果不可靠：可能报找到，也可能报没找到，即使元素其实在容器里。因此先判断序列是否已按从小到大排好；若尚未有序，不得采信这次查找，应先排序再查。

读入序列和目标 \(x\)。若原序列已是非降序，直接对它做 binary_search 并输出 FOUND 或 MISSING；否则输出 UNRELIABLE。然后将序列升序排序，再 binary_search 一次，输出 FOUND 或 MISSING。

输入格式

第一行两个整数 \(n, x\)。

第二行 \(n\) 个整数。当 \(n=0\) 时本行可以是空行。

输出格式

两行。

第一行：原序列有序则为 FOUND 或 MISSING，无序则为 UNRELIABLE。

第二行：排序后再查的 FOUND 或 MISSING。

样例

输入 #1

10 9
0 1 2 3 4 5 6 7 8 9

输出 #1

FOUND
FOUND

输入 #2

11 9
0 1 2 3 4 5 6 7 8 9 2

输出 #2

UNRELIABLE
FOUND

说明

\(0 \le n \le 1000\)，元素与 \(x\) 的绝对值不超过 \(10^9\)。空序列视为有序，在其中查找任何值都是 MISSING。

样例 #1 已是 \(0\sim 9\) 升序，两次都能找到 \(9\)。样例 #2 在有序的 \(0\sim 9\) 末尾又插了一个 \(2\)，序列被打乱；此时若直接二分，结果未知，必须先排序。排序后 \(9\) 仍在，第二行是 FOUND。