On multidimensional generalization of binary search
arxiv(2024)
摘要
This work generalizes the binary search problem to a d-dimensional domain
S_1×⋯× S_d, where S_i={0, 1, …,n_i-1} and d≥ 1,
in the following way. Given (t_1,…,t_d), the target element to be found,
the result of a comparison of a selected element (x_1,…,x_d) is the
sequence of inequalities each stating that either t_i < x_i or t_i>x_i, for
i∈{1,…,d}, for which at least one is correct, and the algorithm does
not know the coordinate i on which the correct direction to the target is
given. Among other cases, we show asymptotically almost matching lower and
upper bounds of the query complexity to be in Ω(n^d-1/d) and O(n^d)
for the case of n_i=n. In particular, for fixed d these bounds
asymptotically do match. This problem is equivalent to the classical binary
search in case of one dimension and shows interesting differences for higher
dimensions. For example, if one would impose that each of the d inequalities
is correct, then the search can be completed in log_2max{n_1,…,n_d}
queries. In an intermediate model when the algorithm knows which one of the
inequalities is correct the sufficient number of queries is
log_2(n_1·…· n_d). The latter follows from a graph search model
proposed by Emamjomeh-Zadeh et al. [STOC 2016].
更多查看译文
AI 理解论文
溯源树
样例
生成溯源树,研究论文发展脉络
Chat Paper
正在生成论文摘要