# Searching Monotone Arrays: A Survey
## 1 Introduction  
Searching is one of the most basic, frequent and important operations performed in tasks involving computation. A common challenge involves searching to decide whether or not a given real value (termed a key) is present in a given multi-dimensional array of real values. When the search must be performed sequentially and repeatedly by comparing the key with selected entries of the array, obviously it should be carried out as efficiently as possible by minimising the number of comparisons. This classic problem can be viewed as determining the correct dimensional threshold function from a finite class of such functions within the array, based on sequential queries that take the form of point samples. The complexity of such a search is completely dependent on how the array is organised. Clearly, when there is no information available about array organisation, every entry must be examined. An array is termed monotone nondecreasing (nonincreasing) if its entries never decrease (increase) when moving away from the origin along any path parallel to an axis. Without loss of generality, from now on in the present article, the focus is on only monotone nondecreasing arrays. When the array is already sorted so that its entries are monotone nondecreasing, the search for a key can be conducted in a far more efficient manner compared to the unsorted case. The problem addressed here is to search for a given real-valued key in a monotone nondecreasing multi-dimensional real array, that has sizes that are not necessarily equal. The challenge is to identify among all possible suitable search algorithms, one with the lowest complexity, i.e., requiring the minimum number of comparisons in the worst case. The main question being addressed until the end of Section 7 of the present article is to ask if the key is present in the array. Thus, if an instance of the key is found, there is no necessity to identify further possible instances of the key and the search procedure is terminated. The search for all possible occurrences of the key is briefly discussed in Section 8. This important search problem occurs in many computation-related fields, including computational biology, image processing, VLSI design, operations research and statistics [1; 2; 3; 4]. The main contributions of this survey are:  
* an introduction to the problem of searching a (strictly) monotone real array;
* a discussion of known results and the description of worst-case algorithms;
* conclusions that can be drawn from the discussions and descriptions and* proposals for future work on the open problems that have been identified. Currently, asymptotic notation to express the complexity of algorithms is commonly used. However, many of the algorithms described here were formally described and analysed at a time when this notation was not so common. The work of [PERSON] and [PERSON] [5], for example, although using asymptotic notation, proposed exact lower and upper bounds on the number of comparisons necessary to determine the occurrence, or not, of a given element in an ordered array. Since then, many other authors have followed the same practice. Thus, for consistency with many of these works and due to the importance of these bounds in understanding the efficiency of the various algorithms listed here, the analyses of many of them are presented as originally developed by the respective authors. However, sometimes, asymptotic notation is used as a complementary tool for describing the complexity of algorithms. The remainder of this paper is organised as follows. Preliminary notation, terminology and basic concepts are provided in the next section. What has been reported in the open literature on searching arrays to establish if a given key is present is reported in Sections 3-6. The search of vectors (\(d=1\)) is the object of Section 3. Seven different algorithms for this case were identified in the literature, from basic linear search algorithms of non-ordered vectors to binary search of ordered matrices.