2024/04/19 by Dariusz Dereniowski, Dereniowski, Dariusz, Przemysław Gordinowicz +3 · 1 citation
Computer Science · Mathematics · #Combinatorics (math.CO) #Data Management and Algorithms #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Fuzzy Systems and Optimization #Metaheuristic Optimization Algorithms Research
paper · pdf · doi:10.48550/arxiv.2404.13193
openalex publication_date 2024/04/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
This work generalizes the binary search problem to a d-dimensional domain S1×⋯× Sd, where Si=\0, 1, …,ni-1\ and d≥ 1, in the following way. Given (t1,…,td), the target element to be found, the result of a comparison of a selected element (x1,…,xd) is the sequence of inequalities each stating that either ti < xi or ti>xi, 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 Ω(nd-1/d) and O(nd) for the case of ni=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 log2max\n1,…,nd\ queries. In an intermediate model when the algorithm knows which one of the inequalities is correct the sufficient number of queries is log2(n1⋅…⋅ nd). The latter follows from a graph search model proposed by Emamjomeh-Zadeh et al. [STOC 2016].