Searching Monotone Arrays: A Survey

Abstract

Given a monotone ordered multi-dimensional real array A and a real value k, an important question in computation is to establish if k is a member of A by sequentially searching A by comparing k with some of its entries. This search problem and its known results are surveyed, including the case when A has sizes not necessarily equal. Worst case search algorithms for various types of arrays of finite dimension and sizes are reported. Each algorithm has order strictly less than the product of the sizes of the array. Present challenges and open problems in the area are also presented.

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 Linial and Saks [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 Section 3, Section 4, Section 5 and Section 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. The other algorithms are Jump Search (Block Search), Interpolation Search, Exponential Search, Fibonacci Search and Ternary Search and its generalisation (k-nary Search). The search of matrices (when $d=2$) is explored in Section 4. Three algorithms are described: Saddleback Search for the case of balanced matrices and Shen’s and Bird’s algorithms for unbalanced matrices. Two algorithms for searching cuboids ($d=3$), one for the balanced case (the L&S algorithm) and one for the unbalanced case (an extension of Shen’s and Bird’s methods), are described in Section 5. Section 6 contains a description of a search algorithm for hypercubes when $d\ge 4$ (denoted as Cheng-4). Section 7 discusses in some detail aspects of the worst case performance of some of the revised algorithms.

Many of the algorithms mentioned above call a binary search algorithm as a subroutine. This algorithm, as well its history, asymptotic complexity and some of its variants, are discussed in detail in Section 3 and Section 7.1. While the main focus of this survey is on the problem of verifying the occurrence or not of a key in monotone arrays, the challenge of searching for all occurrences of the key is also briefly discussed in Section 8. The paper ends with a summary, some concluding remarks and suggestions for future work on problems that remain open, which are presented in Section 9.

2. Preliminaries

Consider a real d-dimensional array $A=\{a(i_1,i_2,\cdots ,i_d)\mid i_1=1,\cdots ,n_1;i_2=1,\cdots ,n_2;\cdots ;i_d=1,\cdots ,n_d\}$, that is monotone nondecreasing in the sense that $a(i_1,i_2,\cdots ,i_d)⩽a(j_1,j_2,\cdots ,j_d)$ if $i_1⩽j_1,i_2⩽j_2,\cdots ,i_d⩽j_d$, for given, independent, sizes $n_1,n_2,\cdots ,n_d\in {\mathbb{Z}}^{+}$, (i.e., the entries of A are nondecreasing along its dimensions). A can be thought of as equivalent to the product of the chains $\left[n_1\right],\left[n_2\right],\cdots ,\left[n_d\right]$ of the partially ordered sets $\{1,\cdots ,n_1\},\{1,\cdots ,n_2\},\cdots$, $\{1,\cdots ,n_d\}$.

A d-dimensional array A can be also defined by the indexes of its lower corner and upper corner as $A((1,1,\dots ,1),\dots ,(n_1,n_2,\dots ,n_d))$. Similarly, a d-dimensional subarray of A is defined as $A(({\ell }_1,{\ell }_2,\dots ,{\ell }_d),\dots ,(r_1,r_2,\dots ,r_d))$, where $1⩽{\ell }_i⩽r_i⩽n_i$, for all $1⩽i⩽d$.

The problem discussed here involves searching A in order to establish whether or not a given key $x\in \mathbb{R}$ is a member of A. It is assumed that the search must be carried out by sequentially comparing x with selected entries $a(i_1,i_2,\cdots ,i_d)\in A$. The purpose of such comparisons is to eliminate elements of A and search the remaining subarrays in an efficient manner. It is of interest to identify search algorithms that require the minimum number of comparisons in the worst case.

When comparing x and any entry $a(i_1,i_2,\cdots ,i_d)$, one of the three following results must be obtained:

$$x<a(i_1,i_2,\cdots ,i_d),$$

(1)

in which case the entries $a(j_1,j_2,\cdots ,j_d)$ for $j_1⩾i_1,j_2⩾i_2,\cdots ,j_d⩾i_d$, can be discarded; or

$$x=a(i_1,i_2,\cdots ,i_d),$$

(2)

in which case x has been located and the search is terminated; or

$$x>a(i_1,i_2,\cdots ,i_d),$$

(3)

in which case the entries $a(j_1,j_2,\cdots ,j_d)$ for $j_1⩽i_1,j_2⩽i_2,\cdots ,j_d⩽i_d$, can be discarded. It is clear that it is necessary to make two comparisons between x and any entry $a(i_1,i_2,\cdots ,i_d)$ to cover the three possibilities (1)–(3).

Any entry that is discarded by the comparison process as (1) and (3) above (as it cannot possibly be x) is termed redundant. If, in carrying out the comparison process, an entry $a(i_1,i_2,\cdots ,i_d)$ of A, causes A to be divided into at least two nondegenerate subarrays, then this entry is termed a pivot.

An array A is said to be $\alpha$-balanced if $n_i⩽\alpha ·n_{i+1}$, $1⩽i⩽d-1$, for a given $\alpha \in {\mathbb{R}}^{+}$, $1⩽\alpha ⩽6.4$. The use of the constant $6.4$ is justified in the arguments given towards the end of Section 4.2. A 1-balanced array is termed balanced, where $n_1=n_2=\cdots =n_d=n$$(⩾2)$ say, and is a hypercube. If $n_i>6.4·n_{i-1}$, $2⩽i⩽d$, A is termed unbalanced. If the sizes of A are strictly unequal, A is a rectangular hypercuboid. From now on, all cuboids and hypercuboids to be searched will be assumed to be rectangular and the term rectangular will be dropped.

Suppose A is a d-dimensional array with sizes $n_1,\cdots ,n_d$. Let $\mathcal{M}\left(A\right)$ be the the minimum number of comparisons (taken over all possible search algorithms) needed either to establish whether or not a given key x is in A. We denote $\mathcal{M}\left(A\right)$ by.

$$\mathcal{M}\left(A\right)=\left\{\begin{array}{cc}\tau (n,d),\hfill & \mathrm{if}A\mathrm{is}\mathrm{balanced}\mathrm{and}{n}_1=\cdots =n_d=n;\hfill \\ \varphi (n_1,\cdots ,n_d),\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(4)

When calculating the asymptotic time complexity of an algorithm, in general, the constant term in $\mathcal{M}\left(A\right)$ can be neglected. However, if an exact count of the number of comparisons is required, the constant term should be included. This has been done when establishing the time complexity of many of the algorithms described in this survey.

Search efficiency depends upon whether or not A is balanced. A summary of the evolution of the best known search algorithms for the various types of arrays is given in Figure 1.

For 1-dimensional arrays the Binary Search algorithm is worst-case optimal (see Section 3). For balanced 2-dimensional arrays, the Saddleback Search algorithm [1,3,6] is worst-case optimal, and $\tau (n,2)$ is $\mathcal{O}\left(n\right)$. For unbalanced 2-dimensional arrays there are asymptotically worst case optimal algorithms, and $\varphi (n_1,n_2)$ is $\mathcal{O}(n_{2}lg(n_1/n_2))$ [7,8] (see Section 4).

For the general case of balanced d-dimensional arrays with $d⩾3$, Linial and Saks [5] demonstrated that $\tau (n,d)$ is $\mathcal{O}\left(n^{d-1}\right)$ as they proved that

$$c_2\left(d\right)n^{d-1}+o\left(n^{d-1}\right)⩽\tau (n,d)⩽c_1\left(d\right)n^{d-1},$$

(5)

where $c_1\left(d\right)$ is a monotone nonincreasing function that is upper bounded by 2 and $c_2\left(d\right)=\sqrt{(24/\pi )}{d}^{-1/2}+o\left(d^{-1/2}\right)$.

Linial and Saks [5] also demonstrated that for the general case of (possibly unbalanced) arrays, with $1⩽n_1⩽n_2\cdots ⩽n_d$, $\varphi (n_1,\cdots ,n_d)$ is bounded as follows:

$$k_2\left(d\right)n_1\cdots n_{d-1}lg(\frac{n_d}{n_{d-1}}+1)⩽\varphi (n_1,\cdots ,n_d)⩽k_1\left(d\right)n_1\cdots n_{d-2}lg(\frac{n_d}{n_{d-1}}+1),$$

(6)

where $k_1\left(d\right)$ and $k_2\left(d\right)$ are functions, with $k_1\left(d\right)$ monotone nonincreasing and $k_2\left(d\right)=c_2\left(d\right)k_2(d-1)/2^d$, and $lg\left(n\right)={log}_2\left(n\right)$. The proofs of the upper bounds on $\tau \left(A\right)$ in the right-hand side of (5) and (6) were established inductively by the authors by partitioning A into n isomorphic copies of its ($d-1$)-dimensional subarrays, each consisting of all entries that have identical $d^{th}$ coordinates. The Linial and Saks algorithm [5] for balanced 3-dimensional arrays will be discussed in Section 5.

Cheng et al. [9] proposed an algorithm for d-dimensional hypercubes, for $d⩾4$ (see Section 6). Their algorithm has worst case performance upper bounded as follows:

$$\tau (n,d)⩽\left(\frac{d}{d-1}\right)n^{d-1}+\mathcal{O}\left(n^{d-2}\right).$$

(7)

3. The Search of Vectors $(\mathit{d}=\mathbf{1})$

When $d=1$ and $n_1=n$ say, A is a monotone vector (a totally ordered set). Many of the monotone vector search methods mentioned below are based on comparisons of keys and have been described in detail by Knuth [10].

The Linear (or Sequential) Search algorithm (see the pseudocode in Algorithm 1) is a basic method for finding a key within A, whether A is ordered or not. The algorithm starts at the leftmost element of A and iteratively compares the key x with each element of A. The search stops when either x matches an element of A or when all the elements have been tested. Its running time and number of comparisons are, in the worst case, linear in n.

Algorithm 1 LINEAR SEARCH$(A,x)$

Input: Array $A(1,\cdots ,n)$ and key $x\in \mathbb{R}$.

Output: True if $x\in A$ or False otherwise.

1. $i\leftarrow 1$;

2. while $(i⩽n)$do

3.   if ($x=A\left[i\right]$) then

4.     return true.

5.   else

6.     $i\leftarrow i+1;$

7.   end if

8. end while

9. return false.

The Jump Search algorithm [11], also known as Block Search [12], check fewer elements of an ordered array $A(1,\cdots ,n)$ than the Linear Search, by jumping ahead blocks of a fixed number m of elements. It verifies the elements of A in the indexes $1,1+m,1+2m,\cdots ,1+km$. Once is determined that $A[1+(k-1\left)m\right]<x<A[1+km]$, a linear search is done in the interval $(1+(k-1)m,1+km)$ to check if any of these elements is equal the key x. Its pseudocode is shown in Algorithm 2.

Algorithm 2 JUMP SEARCH$(A,x,step)$

Input: Array $A(1,\cdots ,n)$ and key $x\in \mathbb{R}$.

Output: True if $x\in A$ or False otherwise.

1. $i\leftarrow 1$;

2. $j\leftarrow step+1$;

3. while $(j<n)$ and$\left(A\right[j]<x)$do

4.    $i\leftarrow j;$

5.    $j\leftarrow j+step;$

6.    if ($j>n$) then

7.      $j\leftarrow n+1;$

8.     end if

9. end while

10. while $(i<j)$ do

11.      $i\leftarrow i+1;$

12.      if ($x=A\left[i\right]$) then

13.   return true.

14.   end if

15. end while

16. return false.

Shneiderman [11] shown that the optimal value of the jump size is $m=\sqrt{n}$. Therefore, if the cost of a jump is $c_j$, and the cost of a sequential search is $c_s$, then the optimum jump size is $\sqrt{(c_j/c_s)n}$ and the search cost is $\tau (n,1)=\sqrt{\left(c_j{c}_s\right)n}$. Shneiderman also describes some variations of this algorithm, as the multi-level jumping or the variable jump size.

Jump Search traverses the array back only once, that can be an advantage in situations where jumping back is costly. Note that Binary Search (the next described algorithm), in the worst case, may require up to $\mathcal{O}(logn)$ back jumps!

The Binary Search algorithm begins with the vector A as the initial search interval, and repeatedly divides the current search interval into two parts that are either of the same length or differ in length by one unit. If the key x is lower than the entry in the “middle” position of the interval (this situation is depicted in Figure 2, where p is the “middle” position), the search space is narrowed to its lower half (positions 1 to $p-1$). If the key x is greater than the mentioned entry, the interval it is narrowed to the upper half (positions $p+1$ to n). The pseudocode of binary search is given in Algorithm 3. It is straightforward to show that the asymptotic complexity of this version of the algorithm is

$$\tau (n,1)=2\lfloor log\left(n\right)\rfloor +1=\mathcal{O}(log(n\left)\right).$$

(8)

However, it is not strictly necessary to compare the key x with the element at position p at each iteration of the search loop. An alternative approach, also commonly used, just checks to see if $x\ne p$. If this is not so, p is returned and the procedure is terminated. Otherwise, p is retained in the search space, which will eventually shrink to p when $p=x$. However, after exiting the loop, i.e., after the search space is completely exhausted, it is necessary to compare the final element in the space with x. The asymptotic implications of assuming that each iteration requires only one comparison are explored in Section 7.1.

Algorithm 3 BINARY SEARCH$(A,x)$

Input: Array $A(1,\cdots ,n)$ and key $x\in \mathbb{R}$.

Output: True if $x\in A$ or False otherwise.

1. $i\leftarrow 1$;

2. $j\leftarrow n$;

3. while $(i⩽j)$do

4.    $p\leftarrow \lfloor \frac{i+j}{2}\rfloor$;

5.    if ($x=A\left[p\right]$) then

6.      return true;

7.    else if ($x<A\left[p\right]$) then

8.      $j\leftarrow p-1;$

9.    else

10.      $i\leftarrow p+1;$

11.     end if

12. end while

13. return false.

The discovery of binary search, also known as logarithmic, divide-and-conquer or bisection search, is attributed by Knuth [10] to Inakibit-Anu of Uruk in 200BC. Binary search was mentioned by Mauchly [13] in what may have been the first published discussion of non-numerical programming methods, but one of the first formal descriptions of it was given by Steinhaus [14]. Furthermore, Sandelius [15] noted that binary search is also optimal in the average case, as cited by Reingold [16].

This history of the evolution of the Binary Search algorithm and its related bibliography, as well as of some other search algorithms listed later here, are described in detail by Knuth [10]. Dijkstra [17] also produced an interesting review of the evolution of the binary search design, from an algorithmic point of view.

Some of these earlier versions of binary search considered only the case where the length of A is a power of 2. At that time the method had become well known, but no one appeared to have reported what should be done to accommodate a general $n\in {\mathbb{Z}}^{+}$ [15,18,19,20]. It seems that Lehmer [21] was the first to publish a Binary Search algorithm that worked for all n. Lesuisse [22] provides a detailed analysis of various published versions of the binary search algorithm.

In these versions of binary search the position of the central element was calculated and, in the case of fractional values, the position was set to the largest integer smaller than the calculated value. If the sequence contained duplicates of the key value, the first occurrence to the left of the calculated position was found. Bottenbruch [23] presented a variation of the algorithm, that is nowadays most common. Setting the position to the smallest integer greater than or equal to the calculated fractional value, the Bottenbruch algorithm adjusts the left pointer, which initially references the first position of the search, to the next position of the central element whenever the key is greater than or equal to this element. Unlike earlier versions, Bottenbruch’s algorithm finds the rightmost occurrence of a given key when the sequential search identifies duplicate entries of the key. Iverson [24] also proposed a version of binary search for every $n\in {\mathbb{Z}}^{+}$, but without considering the possibility of an unsuccessful search. Knuth [25] presented the same algorithm as an example of using an automated system for drawing flowcharts.

Ternary search [26] (also known as dual-pivot binary search [27]) is a divide and conquer algorithm similar to binary search. In this algorithm, the original array is initially divided into three parts of sizes as close as possible to each other. These segments are usually delimited by positions $p_1=1+\lfloor (n-1)/3\rfloor$ and $p_2=n-\lfloor (n-1)/3\rfloor$ (see the pseudocode in Algorithm 4). By testing the values at these two positions it is possible to discard $\frac{2}{3}$ of the array and proceed with the same approach on the remaining $\frac{1}{3}$ of the array. Since a larger portion of the array’s elements are discarded, it may appear that ternary search is faster than binary search. In fact, both algorithms have asymptotic time complexity of $\mathcal{O}(lgn)$. However, ternary search uses more comparisons than binary search, which adds greater constants to its asymptotic complexity. Similar arguments are also valid for any other similar higher order search algorithms that are generalised from binary search (i.e. k-nary search, $k>3$). Section 7.1 provides some detail on the complexity analysis of k-nary search.

Algorithm 4 TERNARY SEARCH$(A,x)$

Input: Array $A(1,\cdots ,n)$ and key $x\in \mathbb{R}$.

Output: True if $x\in A$ or False otherwise.

1. $i\leftarrow 1$;

2. $j\leftarrow n$;

3. while $(i⩽j)$do

4.    $p_1\leftarrow i+⌊\frac{(j-i)}{3}⌋$;

5.    $p_2\leftarrow j-⌊\frac{(j-i)}{3}⌋$;

6.    if ($x=A\left[p_1\right]$) then

7.       return true.

8.     else if ($x=A\left[p_2\right]$) then

9.       return true.

10.     else if ($A\left[p_1\right]>x$) then

11.        $j\leftarrow p_1-1;$

12.      else if ($A\left[p_2\right]<x$) then

13.         $i\leftarrow p_2+1;$

14.      else

15.        $i\leftarrow p_1+1;$

16.        $j\leftarrow p_2-1;$

17.    end if

18. end while

19. return false.

The Interpolation Search algorithm, due to Peterson [28], performs similarly to binary search but unlike it, which always checks the intermediate element of the search space, the interpolation search can check different elements according to the value of the key and the statistical distribution of the elements in the array A. For example, it is likely that the interpolation search will start at an element either near the index n (when the key is closer to $A\left[n\right]$), or near the index 1 (when the key is closer to $A\left[1\right]$.) The pseudocode is shown in Algorithm 5. When the values in the array A are uniformly distributed, the interpolation search has a performance superior of that of binary search. Perl et al. [29] showed that this algorithm requires on the average $loglogn$ array accesses to check if a key is present in the array, assuming that the n array entries are uniformly distributed.

Algorithm 5 INTERPOLATION SEARCH$(A,x)$

Input: Array $A(1,\cdots ,n)$ and key $x\in \mathbb{R}$.

Output: True if $x\in A$ or False otherwise.

1. $i\leftarrow 1$;

2. $j\leftarrow n$;

3. while $(i⩽j) \mathbf{and} \left(A\right[i]\ne A[j\left]\right) \mathbf{and} \left(A\right[i]⩽x⩽A[j\left]\right)$do

4.    $p\leftarrow i+⌊\frac{(j-i)}{\left(A\right[j]-A[i\left]\right)}⌋·(x-A\left[i\right])$;

5.    if ($x=A\left[p\right]$) then

6.      return true.

7.    else if ($x<A\left[p\right]$) then

8.      $j\leftarrow p-1;$

9.    else

10.      $i\leftarrow p+1;$

11.    end if

12. end while

13. if ($i⩽n$) and ($A\left[i\right]=x$) then

14.    return true

15. else

16.    return false.

17. end if

The Exponential Search algorithm is attributed to Bentley and Yao [30]. This search algorithm involves a preliminary step of finding a small range of elements of the array A (potentially containing the key x) and a secondary step of performing a binary search in this limited range of elements. The first step starts with a subarray of size 1, compares its unique element with the key x, then, if necessary, compares a subarray of size 2, then of 4, and so on, until the last element, index i say, of the current subarray is not greater than the key x. At the end of this step, the key can only be present between the indexes $i/2$ and i. Therefore, a binary search is carried out in this range. The pseudocode of this algorithm is shown in Algorithm 6. Exponential Search is particularly useful for unbounded arrays, that is, where the size of the array to be searched is infinite. This search also works better than binary search for bounded arrays when the key x is closer to the first element of the array.

Algorithm 6 EXPONENTIAL SEARCH$(A,x)$

Input: Array $A(1,\cdots ,n)$ and key $x\in \mathbb{R}$.

Output: True if $x\in A$ or False otherwise.

1. $i\leftarrow 1$;

2. if ($x=A\left[i\right]$) then

3.    return true.

4. end if

5. while $(i⩽n)$ and $(x>A[i\left]\right)$ do

6.    $i\leftarrow i·2$;

7. end while

8. return BINARY SEARCH$(A(\lfloor \frac{i}{2}\rfloor +1,min\{i,n\}),x)$.

Fibonacci Search (Ferguson [31]) splits the array A into two subarrays with sizes that are consecutive Fibonacci numbers, which are defined as:

$$F_m=\left\{\begin{array}{cc}m,\hfill & \mathrm{if}0⩽m<2;\hfill \\ F_{m-1}+F_{m-2},\hfill & \mathrm{if}m⩾2.\hfill \end{array}\right.$$

(9)

This search first finds the smallest Fibonacci number, the $m^{th}$ one say, greater than or equal to n, then uses the ${(m-2)}^{th}$ Fibonacci number as the index of the array element to be compared with the key (if it is a valid index). While there are still elements to be inspected, the limits of the subarray that must be searched are calculated based on the three consecutive Fibonacci numbers currently used. The pseudocode shown in Algorithm 7, uses the $m^{th}$ Fibonacci number just defined and a variable offset to help to discard the unnecessary positions of the array A.

Algorithm 7 FIBONACCI SEARCH$(A,x)$

Input: Array $A(1,\cdots ,n)$ and key $x\in \mathbb{R}$.

Output: True if $x\in A$ or False otherwise.

1. $f\leftarrow F_m$;

2. $f_1\leftarrow F_{m-1}$;

3. $f_2\leftarrow F_{m-2}$;

4. $offset\leftarrow 0$;

5. while $(f>1)$do

6.    $p\leftarrow min\{offset+f_2;n\}$;

7.    if ($x>A\left[p\right]$) then

8.      $f\leftarrow f_1$;

9.      $f_1\leftarrow f_2$;

10.      $f_2\leftarrow f-f_1$;

11.      $offset\leftarrow p$;

12.    else if ($x<A\left[p\right]$) then

13.      $f\leftarrow f_2$;

14.      $f_1\leftarrow f_1-f_2$;

15.      $f_2\leftarrow f-f_1$;

16.    else

17.       return true.

18.    end if

19. end while

20. if $(f_1>0)$ and ($x=A[offset+1]$) then

21.    return true;

22. else

23.    return false.

24. end if

4. The Search of Matrices $(\mathit{d}=\mathbf{2})$

As illustrated in Figure 3, throughout this survey the corners $(1,1)$, $(n,1)$, $(1,n)$ and $(n,n)$ of 2-dimensional arrays are termed: southwest (SW), northwest (NW), southeast (SE) and northeast (NE) corners, respectively.

4.1. Balanced Matrices

When $d=2$ and A is balanced ($n_1=n_2=n$), the Saddleback Search algorithm [1,3,6] is worst-case optimal. Saddleback search begins by comparing the key x with the last entry in the first row of A (corner SE in Figure 3). If x is lower than this entry then x cannot be in the column n of A and this column is discarded. If x is greater than this entry then x cannot be in the row 1 of A and this row is discarded. The process is repeated, always comparing x with the last entry in the first row of what remains of A until either x is found or all of the entries of A have been discarded. The pseudocode of the saddleback search is given in Algorithm 8.

A similar argument is valid when x is compared with the last entry in the first column (the corner NW in Figure 3). In fact, at each iteration of the saddleback search either of the entries in the current NW and SE corners can be randomly chosen to be compared with the key x, with the same worst-case performance.

Algorithm 8 SADDLEBACK SEARCH$(A,x)$

Input: Array $A\left(\right(1,1),\cdots ,(n,n\left)\right)$ and key $x\in \mathbb{R}$.

Output: True if $x\in A$ or False otherwise.

1. $i\leftarrow 1$;

2. $j\leftarrow n$;

3. while $(i⩽n)$ and $(j⩾1)$do

4.    if ($x=A(i,j)$) then

5.      return true.

6. else if ($x>A(i,j)$)

7.      $i\leftarrow i+1;$

8.   else

9.      $j\leftarrow j-1;$

10.   end if

11. end while

12. return false.

The above arguments lead to the following result for the worst case performance of saddleback search, according to Graham and Karp, 1968 (quoted in [5]):

$$\tau (n,2)=2n-1.$$

(10)

The fact that this number is worst case optimal is easily seen through an adversary argument by setting A as:

$$a(i,j)=\left\{\begin{array}{cc}-\infty ,\hfill & \mathrm{if}i+j⩽n,\hfill \\ +\infty ,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(11)

If any search procedure fails to compare x with any entry $a(i,j)$ with $i+j=n$ or $i+j=n+1$ (a total of $n-1+n=2n-1$ entries), then that entry could contain x while still allowing A to be monotone. Thus, any search procedure must make at least $2n-1$ comparisons. Hence, saddleback search is a best possible worst-case procedure. The above argument also holds when A is set as:

$$a(i,j)=\left\{\begin{array}{cc}-\infty ,\hfill & \mathrm{if}i+j⩽n+1,\hfill \\ +\infty ,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(12)

4.2. Unbalanced Matrices

In this section it is assumed that $d=2$ and A is unbalanced, i.e., $n_1<n_2$. There is the possibility of searching each of the $n_1$ rows individually by binary search. This procedure requires $\mathcal{O}(n_{1}lg\left(n_2\right))$ comparisons, which is worst case optimal only if $n_1=o\left(n_2\right)$ [8]. Alternatively, one could divide A into $\lceil n_2/n_1\rceil$ submatrices of dimensions at most $n_1\times n_1$ and apply saddleback search (as explained in Section 4.1) to each of them. This procedure is worst case optimal only if $n_1=\Theta \left(n_2\right)$. On the other hand, applying saddleback search in the whole matrix lead to a worst case performance of

$$\tau (n_1,n_2)=n_1+n_2-1.$$

(13)

Since A is unbalanced ($n_2>6.4·n_1$, as justified towards the end of Section 4.2.2), none of the aforementioned approaches performs very well in the worst case.

Fortunately, there are search algorithms for unbalanced arrays that are asymptotically worst case optimal, with $\tau (n_1,n_2)=\mathcal{O}(n_{1}lg(n_2/n_1))$ [7,8]. These algorithms work by iteratively applying binary search to selected vectors of A to identify pivots. The pivots are used to eliminate redundant entries and to divide the remainder of A into (smaller) subarrays that are searched subsequently. At each iteration, the algorithms eliminate a maximal number of redundant entries.

4.2.1. Shen’s Algorithms

Shen [8] proposed both diagonal-searching and row-searching matrix partitioning algorithms, which are asymptotically worst case optimal for unbalanced arrays. A slightly different algorithm from the latter, which uses linear search instead of binary search in the row-searching step, but achieving the same asymptotic complexity, was proposed previously by Aggarwal et al. [32] in a context of geometric applications.

The pseudocode of Shen’s row-searching procedure is given in Algorithm 9. The algorithm starts by comparing the key x with the two extremes of the middle row of an array $A((1,1),\cdots ,(n_1,n_2))$, initially being ${\ell }_1=1$, ${\ell }_2=1$, $r_1=n_1$ and $r_2=n_2$, which has row index i, say. If $x<a(i,1)$, the submatrix $A((i,1),\dots ,(n_1,n_2))$ is discarded. If $x>a(i,n_2)$, the submatrix $A((1,1),\dots ,(i,n_2))$ is discarded. Otherwise, a binary search on row i generates a pivot $a(i,j)$ that allows the submatrices $A_{SW}=A((1,1),\dots ,(i,j))$ and $A_{NE}=A(i,j+1),\dots ,(n_1,n_2))$ to be discarded. The algorithm proceeds by searching recursively on submatrices $A_{NW}=A((i+1,1),\dots ,(n_1,j))$ and $A_{SE}=A((1,j+1),\dots ,(i-1,n_2))$. The submatrices $A_{NW}$, $A_{NE}$, $A_{SW}$ and $A_{SE}$ are depicted in Figure 4a.

Algorithm 9 SHEN$(A,x)$

Input: Array $A(({\ell }_1,{\ell }_2),\cdots ,(r_1,r_2))$ and key $x\in \mathbb{R}$.

Output: True if $x\in A$ or False otherwise.

1. $found\leftarrow$ false;

// Stop conditions.

2. if $(r_1-{\ell }_1+1<4)$ or $(r_2-{\ell }_2+1<4)$ then

3.    Use BinarySearch in rows/columns; exit;

4. end if

5. $i\leftarrow \lfloor \frac{{\ell }_1+r_1}{2}\rfloor$;

6. if ($x<a(i,{\ell }_2)$) then

7.      $found\leftarrow$ SHEN($A(({\ell }_1,{\ell }_2),\cdots ,(i-1,r_2)),x$);       // Recursion on submatrix SW-SE.

8. else if ($x>a(i,r_2)$) then

9.      $found\leftarrow$ SHEN($A((i+1,{\ell }_2),\cdots ,(r_1,r_2)),x$);     // Recursion on submatrix NW-NE.

10. else

11.      $j\leftarrow$ BinarySearch($A((i,{\ell }_2),\cdots ,(i,r_2)),x$);       // $a(i,j)⩽x<a(i,j+1)$?

12.      if ($x\ne a(i,j)$) then

13.         $found\leftarrow$ SHEN($A((i+1,{\ell }_2),\cdots ,(r_1,j)),x$);         // Recursion on NW.

14.         $found\leftarrow$ SHEN($A(({\ell }_1,j+1),\cdots ,(i-1,r_2)),x$);          // Recursion on SE.

15.      else

16.         $found\leftarrow$ True;

17.      end if

18. end if

19. return $found$.

Algorithm 9 has time complexity given by the following recurrences:

$$\varphi (n_1,n_2)=\left\{\begin{array}{cc}\mathcal{O}(lg{n}_1),\hfill & \mathrm{if}{n}_2=1;\hfill \\ \mathcal{O}(lg{n}_2),\hfill & \mathrm{if}{n}_1=1;\hfill \\ \varphi (\lfloor n_1/2\rfloor ,j)+\varphi (\lfloor n_1/2\rfloor ,n_2-j)+\mathcal{O}(lg\left(n_2\right)),\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(14)

In the diagonal-searching procedure, Shen’s algorithm [8] divides the $n_1\times n_2$ matrix A into $\lceil \frac{n_2}{n_1}\rceil$ submatrices of dimensions at most $n_1\times n_1$ and uses binary search to find a pivot element $a\left(i,j\right)$ on the main diagonal of the “middle” submatrix such that $a\left(i,j\right)<x<a\left(i+1,j+1\right)$. This pivot splits the matrix into four possible non empty submatrices $A_{NW}$, $A_{NE}$, $A_{SW}$ and $A_{SE}$, as depicted in Figure 4b. Similarly to the row searching schema, the pivot $a\left(i,j\right)$ allows both submatrices $A_{NE}$ and $A_{SW}$ to be discarded. Therefore, the search only needs to continue on the two matrices $A_{NW}=A((i+1,1),\dots ,(n_1,j))$ and $A_{SE}=A((1,j+1),\dots ,(i,n_2))$ of reduced size.

Shen’s diagonal-searching procedure has time complexity given by the following recurrences:

$$\varphi (n_1,n_2)=\left\{\begin{array}{cc}\mathcal{O}(lg{n}_1),\hfill & \mathrm{if}{n}_2=1;\hfill \\ \mathcal{O}(lg{n}_2),\hfill & \mathrm{if}{n}_1=1;\hfill \\ \mathcal{O}\left(n_1\right),\hfill & \mathrm{if}{n}_1=n_2\hfill \\ \varphi (n_1-i,j)+\varphi (i,n_2-j)+\mathcal{O}(lg\left(n_2\right)),\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(15)

Shen showed that Algorithm 9 has worst case performance when submatrices $A_{NW}$ and $A_{SE}$ have the same size, that is, $j=\lfloor n_2/2\rfloor$. Similarly, in the diagonal-searching procedure the worst case occurs when $i=\lceil n_1/2\rceil$. Therefore, given (14) and (15), both algorithms approaches have worst case time complexity of $\varphi (n_1,n_2)=\mathcal{O}(n_{1}lg(2n_2/n_1))=\mathcal{O}(n_{1}lg(n_2/n_1))$, which is asymptotically optimal.

4.2.2. Bird’s Algorithm

Bird’s Algorithm [7] uses a row-searching approach that is similar to that of Shen. A binary search is conducted on the middle row of A to find a pivot $a(i,j)$ such that $a\left(i,j\right)⩽x<a\left(i,j+1\right)$. If $x>a\left(i,j\right)$ then the search continues only on the two matrices $A_{NE}$ and $A_{SE}$ of reduced size. The algorithm does not perform the two first comparisons of Shen’s Algorithm (Lines 6 and 8), proceeding directly to search in the two submatrices of reduced size (Lines 13 and 14).

Bird provided the following recurrence to express the asymptotic worst case of his algorithm:

$$\varphi (n_1,n_2)=\left\{\begin{array}{cc}\mathcal{O}(lg{n}_1),\hfill & \mathrm{if}{n}_2=1;\hfill \\ \mathcal{O}(lg{n}_2),\hfill & \mathrm{if}{n}_1=1;\hfill \\ 2\varphi (\lceil n_1/2\rceil ,\lceil n_2/2\rceil )+\mathcal{O}(lg\left(n_2\right)),\hfill & \mathrm{otherwise};\hfill \end{array}\right.$$

(16)

and hence has time complexity $\mathcal{O}(n_{1}lg\left(\lceil n_2/n_1\rceil \right))$, which is asymptotically optimal.

We now establish an exact count of the number of comparisons required by Bird’s algorithm in the worst case. Suppose that the algorithm is applied to a 2-dimensional $n_1\times n_2$ array with $n_1⩽n_2$. Since $n_1$ ($n_2$) is an integer in a closed range delimited by two consecutive powers of two, the complexity analysis can be done considering that the worst case occurs when $n_1$ ($n_2$) is the upper bound of the range, as assumed in the following development:

$$\begin{array}{cc}\hfill \varphi (n_1,n_2)& ⩽lg{n}_2+2\varphi (n_1/2,n_2/2)\hfill \\ \hfill & =lg{n}_2+2lg(n_2/2)+2^2\varphi (n_1/2^2,n_2/2^2)\hfill \\ \hfill & ⋮\hfill \\ \hfill & =lg{n}_2+2lg(n_2/2)+2^{2}lg(n_2/2^2)+\cdots +2^{i-1}lg(n_2/2^{i-1})+\hfill \\ \hfill & 2^i\varphi (n_1/2^i,n_2/2^i)\hfill \\ \hfill & =lg{n}_2+2(lg{n}_2-lg2)+2^2(lg{n}_2-lg{2}^2)+\cdots +2^{i-1}(lg{n}_2-lg{2}^{i-1})+\hfill \\ \hfill & 2^i\varphi (n_1/2^i,n_2/2^i)\hfill \\ \hfill & =lg{n}_2\sum _{k=0}^{i-1}{2}^k-\sum _{k=0}^{i-1}k{2}^k+2^i\varphi (n_1/2^i,n_2/2^i).\hfill \end{array}$$

When $n_1/2^i=1$, $n_2/2^i>1$. Thus $i=lg{n}_1$ and $\varphi (n_1/2^i,n_2/2^i)=\varphi (1,n_2/2^{lg{n}_1})=\varphi (1,n_2/n_1)=lg(n_2/n_1)$. Then:

$$\begin{array}{cc}\hfill \varphi (n_1,n_2)& ⩽lg{n}_2\sum _{k=0}^{i-1}{2}^k-\sum _{k=0}^{i-1}k{2}^k+2^i\varphi (n_1/2^i,n_2/2^i)\hfill \\ \hfill & =lg{n}_2\sum _{k=0}^{lg{n}_1-1}{2}^k-\sum _{k=0}^{lg{n}_1-1}k{2}^k+2^{lg{n}_1}lg(n_2/n_1)\hfill \\ \hfill & =lg{n}_2\left(2^{lg{n}_1}-1\right)-\left(2^{lg{n}_1}lg{n}_1-2^{lg{n}_1}2+2\right)+2^{lg{n}_1}lg(n_2/n_1)\hfill \\ \hfill & =lg{n}_2\left(n_1-1\right)-\left(n_{1}lg{n}_1-2n_1+2\right)+n_{1}lg{n}_2-n_{1}lg{n}_1\hfill \\ \hfill & =2n_{1}lg{n}_2-2n_{1}lg{n}_1-lg{n}_2+2n_1-2\hfill \\ \hfill & =2n_{1}lg{n}_2-2n_{1}lg{n}_1+2n_1-lg{n}_2-lg4\hfill \\ \hfill & =2n_{1}lg(n_2/n_1)+2n_1-lg\left(4n_2\right).\hfill \end{array}$$

Thus, Bird’s algorithm has worst case performance

$$\varphi (n_1,n_2)=2n_{1}lg\left(\frac{n_2}{n_1}\right)+2n_1-lg\left(4n_2\right).$$

(17)

A comparison of (13) and (17) leads easily to the following deductions (which also establish the parameter $6.4$ as the basis for defining the phrase unbalanced array). If $n_1⩽n_2⩽6.4·n_1$, Bird’s algorithm has an inferior worst case performance than that of saddleback search. Conversely, if $6.4·n_1<n_2$, and thus the array is unbalanced, the algorithm has a better worst case performance than saddleback search.

4.3. The Location of Pivots when Searching a Row of a 2-d Matrix

The purpose of this subsection is to establish the worst case performance of binary search when it is used as a subroutine to search the middle row of a given 2-dimensional monotone real array A as part of an algorithm that is designed to search A for a given key x. Bird’s algorithm [7] and the first algorithm of Shen [8]) utilise such a subroutine. More specifically, suppose that $A_{n_1\times n_2}$ with $n_1⩽n_2$, is such a given array and that binary search is applied to the $i^{\mathrm{th}}$ row of A, for a given i, $1⩽i⩽n_1$. That is, the entries, $a(i,q)$, $q=1,\cdots ,n_2$; are to be searched.

We assume from now on that the binary search of row i did not find an instance of the key x, but returned the entry $a(i,j)$ ($\ne x$), for some column j of A, $1⩽j⩽n_2$ (see Algorithm 3). In this case $a(i,j)$ is used as a pivot by comparing it with x in order to discard the parts of A that now become redundant in the sense that x cannot be a member of them. Let $f(i,j)$ be the number elements of A that are thus discarded. The issue to be addressed involves identifying for a given i, which j, where $1⩽j⩽n_2$, corresponds to the worst case in the sense that using $a(i,j)$ as the pivot causes the least number of elements of A, to be discarded. That is, j is worst case if $j=argminf(i,j)$.

As will be seen later in the present subsection, it has been established that when:

(i)

$n_1$ is odd, $f(i,j)$ is independent of j.

(ii)

$n_1$ is even and $i=n_1/2$, $f(i,j)$ is minimal when j is maximal.

(iii)

$n_1$ is even and $i=n_1/2+1$, $f(i,j)$ is minimal when j is minimal.

The above results are now investigated in some detail.

If $j=1$ ($j=n_2$), then $x<a(i,q)$ ($x>a(i,q)$) for $q=1,\cdots ,n_2$; and the rectangle $A[(i,1),\cdots ,(n_1,n_2)]$ ($A[(1,1),\cdots ,(i,n_2)]$) is redundant and can be discarded. Otherwise, if $1<j<n_2$, then both $x>A[i,j]$ and $x<A[i,j+1]$ hold and the redundant area comprises the two rectangles: $A_{NE}=A[(i,j+1),\cdots ,(n_1,n_2)]$ and $A_{SW}=A[(1,1),\cdots ,(i,j)]$. Figure 5a may aid the understanding of the following reasoning. Examples are given in

Table 1. Case 1. $n_1$ is odd.

Row i	Column j
	1	2	3	4	5	6	7	8
7	1	1	1	1	1	1	1	1
6	1	1	1	1	1	1	1	1
5	1	1	1	1	1	1	1	1
4	0	0	0	0	0	0	0	0
3	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0

and

Table 2. Cases 2 (a) and 2(b). $n_1$ is even with (a) $i=3$ and (b) $i=4$.

Row i	Column j
	1	2	3	4	5	6	7	8
6	1	1	1	1	1	1	1	1
5	1	1	1	1	1	1	1	1
4	1	1	1	1	1	1	1	1
3	0	0	0	0	0	0	0	0
2	0	0	0	0	0	0	0	0
1	0	0	0	0	0	0	0	0

in which a zero (unit) entry represents a number less than (greater than) x.

The total number $f(i,j)$ of redundant entries defined by the ordered pair of indexes $(i,j)$ is:

$$f(i,j)=\left\{\begin{array}{cc}(n_1-(i-1))n_2,\hfill & \mathrm{if}j=1;\hfill \\ n_{2}i,\hfill & \mathrm{if}j=n_2;\hfill \\ ij+(n_1-(i-1))(n_2-j),\hfill & \mathrm{if}1<j<n_2.\hfill \end{array}\right.$$

(18)

A simple algebraic rearrangement of the case $1<j<n_2$ leads to:

$$f(i,j)=(n_1+1)n_2-n_{2}i-(n_1+1-2i)j.$$

(19)

Clearly, the number of entries left to be searched is $g(i,j)=n_1{n}_2-f(i,j)$, which after some algebraic rearrangement leads to:

$$g(i,j)=\left\{\begin{array}{cc}(i-1)n_2,\hfill & \mathrm{if}j=1;\hfill \\ (n_1-i)n_2,\hfill & \mathrm{if}j=n_2;\hfill \\ n_{2}i+(n_1+1-2i)j-n_2,\hfill & \mathrm{if}1<j<n_2.\hfill \end{array}\right.$$

(20)

Suppose that the middle row of A is searched (as is done in Bird’s algorithm [7] and in the first algorithm of Shen [8]). The special cases when $j=1$ or $j=n_2$ are such that the values of $f(i,1),g(i,1),f(i,n_2)$ and $g(i,n_2)$ do not depend on the index j and are treated separately at the end of this subsection. We first deal with the case when $1<j<n_2$ and construct the functions$f(i,j)$ and $g(i,j)$, on the basis of the parity of $n_1$.

• Case 1 ($n_1$ is odd):

The index i is uniquely specified as $i=\lceil n_1/2\rceil$ and thus $i=(n_1+1)/2$. Substituting i in (19), It can be seen that the number of redundant entries reduces to $f(i,j)=(n_1+1)n_2/2$, which is independent of j. Thus, it does not matter which entry j of the $i^{\mathrm{th}}$ row of A is identified by the binary search as the pivot (including the cases $j=1$ and $j=n_2$). Hence, the number $g(i,j)$ of entries left to be searched is invariant, where

$$g(i,j)=\frac{(n_1-1)n_2}{2}.$$

(21)

This case is illustrated in Table 1, where $n_1=7,n_2=8,i=4,f(4,j)=32$ and $g(4,j)=24$, $j=1,\cdots ,8$.

• Case 2 ($n_1$ is even):

The index i can be specified as either $i=\lceil n_1/2\rceil$ ($i=n_1/2$) or $i=\lceil n_1/2\rceil +1$ ($i=n_1/2+1$). For either specification, an obvious task is to identify the column j of A that corresponds to the worst case, where the least number of entries is made redundant. This happens when, for a specified row i, binary search returns an index j corresponding to $argmin\left(f\right(i,j\left)\right)$ or, equivalently, to $argmax\left(g\right(i,j)$). The two specifications of i are now settled.

• Case 2(a) ($n_1$ is even and $i=n_1/2$):

It can be seen from (19) that $f(i,j)$ reduces to $(n_1+2)n_2/2-j$, which is minimal when j is as large as possible ($j=n_2-1$). Thus, the number of entries left to be searched is

$$\begin{array}{c}\hfill g(i,j)=\frac{n_1{n}_2}{2}-1.\end{array}$$

(22)

This case is illustrated in Figure 5b.

• Case 2(b) ($n_1$ is even and $i=n_1/2+1$):

Here $f(i,j)$ reduces to $\left(n_1{n}_2\right)/2+j)$, which is minimal when j is as small as possible, i.e., $j=2$. Thus, the number of entries left to be searched is,

$$\begin{array}{c}\hfill g(i,j)=\frac{n_1{n}_2}{2}-2.\end{array}$$

(23)

Note that for the separate cases when the binary search returns either $j=1$ or $j=n_2$ as the pivot, the number of entries left to be searched is $g(i,n_2)=\left(n_1{n}_2\right)/2$, which is higher than those in relations (22) and (23). The cases are illustrated in Table 2, where $n_1=6$ and $n_2=8$. As an example of Case 2($\mathbf{a}$), if $\mathit{i}=\mathbf{3}$ and $\mathit{j}=\mathbf{7}$, then $\mathit{f}(\mathbf{3},\mathbf{7})=\mathbf{25}$ and $\mathit{g}(\mathbf{3},\mathbf{7})=\mathbf{23}$. However, if $\mathit{i}=\mathbf{3}$ and $\mathit{j}=\mathbf{1}$, then $\mathit{f}(\mathbf{3},\mathbf{1})=\mathit{g}(\mathbf{3},\mathbf{1})=\mathbf{24}$. As an example of Case 2($\mathit{b}$), if $\mathit{i}=\mathbf{4}$ and $\mathit{j}=\mathbf{2}$, then $\mathit{f}(\mathbf{4},\mathbf{2})=\mathbf{26}$ and $\mathit{g}(\mathbf{4},\mathbf{2})=\mathbf{22}$. However, if $\mathit{i}=\mathbf{3}$ and $\mathit{j}=\mathbf{8}$, then $\mathit{f}(\mathbf{3},\mathbf{8})=\mathit{g}(\mathbf{3},\mathbf{8})=\mathbf{24}$.

5. Searching the Cuboid $(\mathit{d}=\mathbf{3})$

5.1. The Balanced Case (the $\mathit{n}$-Cube)

For the particular case where $\mathit{d}=\mathbf{3}$, and the array is balanced (an $\mathit{n}$-cube), Linial and Saks [5] improved on the bounds in (5) by establishing

$$⌊\frac{\mathbf{3}}{\mathbf{2}}{\mathit{n}}^{\mathbf{2}}⌋⩽\mathbf{\tau }(\mathit{n},\mathbf{3})⩽\frac{\mathbf{3}}{\mathbf{2}}{\mathit{n}}^{\mathbf{2}}+\mathbf{3}\mathit{n}lg(\mathit{n}+\mathbf{2}).$$

(24)

As the authors mention, the lower bound in the left-most expression of (24) can be established as follows. The worst case instance is given by

$$\mathit{a}(\mathit{i},\mathit{j},\mathit{k})=\left\{\begin{array}{cc}-\infty ,\hfill & \mathrm{if}\mathit{i}+\mathit{j}+\mathit{k}⩽\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{1}\mathrm{and}\mathit{n}\mathrm{is}\mathrm{even};\hfill \\ -\infty ,\hfill & \mathrm{if}\mathit{i}+\mathit{j}+\mathit{k}⩽\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{3}/\mathbf{2}\mathrm{and}\mathit{n}\mathrm{is}\mathrm{odd};\hfill \\ +\infty ,\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(25)

For $\mathit{n}$ even, if any search algorithm fails to compare $\mathit{x}$ with any element $\mathit{a}(\mathit{i},\mathit{j},\mathit{k})$, where:

$$\begin{array}{cc}\hfill \mathit{i}+\mathit{j}+\mathit{k}& =\frac{\mathbf{3}}{\mathbf{2}}\mathit{n}+\mathbf{1}\hfill \end{array}$$

(26)

or

$$\begin{array}{cc}\hfill \mathit{i}+\mathit{j}+\mathit{k}& =\frac{\mathbf{3}}{\mathbf{2}}\mathit{n}+\mathbf{2},\hfill \end{array}$$

(27)

then that element could be equal to $\mathit{x}$ even though $\mathit{A}$ is monotone.

For $\mathit{n}$ odd, if any algorithm fails to compare $\mathit{x}$ with any element $\mathit{a}(\mathit{i},\mathit{j},\mathit{k})$, where:

$$\begin{array}{c}\hfill \mathit{i}+\mathit{j}+\mathit{k}=\frac{\mathbf{3}}{\mathbf{2}}\mathit{n}+\frac{\mathbf{3}}{\mathbf{2}}\end{array}$$

(28)

or

$$\begin{array}{c}\hfill \mathit{i}+\mathit{j}+\mathit{k}=\frac{\mathbf{3}}{\mathbf{2}}\mathit{n}+\frac{\mathbf{5}}{\mathbf{2}},\end{array}$$

(29)

then that element could be equal to $\mathit{x}$ even though $\mathit{A}$ is monotone.

It is straightforward to compute the number of elements satisfying (26) and (27). As an illustration, for (26) we must enumerate the number of triples $(\mathit{i},\mathit{j},\mathit{k})$ in the range $\mathbf{1},\cdots ,\mathit{n}$ that sum to $\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{1}$. To do this, one should count the number of triples for which $\mathit{i},\mathit{j},\mathit{k}⩾\mathbf{1}$ and subtract from it the number of triples for which at least one of $\mathit{i},\mathit{j},\mathit{k}>\mathit{n}$.

The number of triples that sum to $\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{1}$ is $\left(\genfrac{}{}{0pt}{}{\mathbf{3}\mathit{n}/\mathbf{2}}{\mathbf{2}}\right)$. The number of triples that sum to $\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{1}$ with a term bigger than $\mathit{n}$ is $\left(\genfrac{}{}{0pt}{}{\mathbf{3}\mathit{n}/\mathbf{2}}{\mathbf{2}}\right)$. Thus, the total is $\left(\genfrac{}{}{0pt}{}{\mathbf{3}\mathit{n}/\mathbf{2}}{\mathbf{2}}\right)-\mathbf{3}\left(\genfrac{}{}{0pt}{}{\mathit{n}/\mathbf{2}}{\mathbf{2}}\right)$, which is $\mathbf{3}{\mathit{n}}^{\mathbf{2}}/\mathbf{4}$.

For the expression in (27) it is necessary to count the number of triples $(\mathit{i},\mathit{j},\mathit{k})$, in the range $\mathbf{1},\cdots ,\mathit{n}$; that sum to $\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{2}$, which is $\left(\genfrac{}{}{0pt}{}{\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{1}}{\mathbf{2}}\right)$. The number of triples that sum to $\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{2}$ with a term bigger than $\mathit{n}$ is $\left(\genfrac{}{}{0pt}{}{\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{1}}{\mathbf{2}}\right)$. Hence the total is $\left(\genfrac{}{}{0pt}{}{\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{1}}{\mathbf{2}}\right)-\mathbf{3}\left(\genfrac{}{}{0pt}{}{\mathit{n}/\mathbf{2}+\mathbf{1}}{\mathbf{2}}\right)$, which is also $\mathbf{3}{\mathit{n}}^{\mathbf{2}}/\mathbf{4}$. Therefore the number of elements satisfying (26) and (27) is $\mathbf{3}{\mathit{n}}^{\mathbf{2}}/\mathbf{2}$. The number of elements satisfying (28) and (29) follows analogously, which is $\lfloor \mathbf{3}{\mathit{n}}^{\mathbf{2}}/\mathbf{2}\rfloor$. Thus the first inequality in (24) is proven.

Linial and Saks [5] established the upper bound in the right-most expression of (24) by constructing an algorithm (termed the L&S Algorithm here) with worst case performance equal to the bound. As the constant of the right-most expression in (24) is positive, the L&S algorithm is asymptotically tight in the worst case. An outline of the algorithm follows. It alternates between applying binary search along a closed path of particular vectors and by applying Saddleback Search described in Section 4.1 for a rectangle, which progressively reduces $\mathit{n}$ by two units at each iteration. At the first stage of the first iteration of the algorithm, binary searches for $\mathit{x}$ are conducted along six vectors that together form what we call the Yellow Brick Road (The Yellow Brick Road is a fictional element in the children’s novel The Wonderful Wizard of Oz by United States author L. Frank Baum (1900)) (YBR) cycle. The simplified diagram in Figure 6a illustrates this cycle, which comprises paths that connect the following entries of $\mathit{A}$: $\mathit{r}=\mathit{a}(\mathit{n},\mathit{n},\mathbf{1})$, $\mathit{s}=\mathit{a}(\mathit{n},\mathbf{1},\mathbf{1})$, $\mathit{t}=\mathit{a}(\mathit{n},\mathbf{1},\mathit{n})$, $\mathit{u}=\mathit{a}(\mathbf{1},\mathbf{1},\mathit{n})$, $\mathit{v}=\mathit{a}(\mathbf{1},\mathit{n},\mathit{n})$ and $\mathit{w}=\mathit{a}(\mathbf{1},\mathit{n},\mathbf{1})$.

The paths of the initial YBR cycle are the vectors that connect the ordered pairs of entries: $(\mathit{r},\mathit{s})$, $(\mathit{s},\mathit{t})$, $(\mathit{t},\mathit{u})$, $(\mathit{u},\mathit{v})$, $(\mathit{v},\mathit{w})$ and $(\mathit{w},\mathit{r})$. These paths can be represented as the vectors: $\langle \mathit{a}(\mathit{n},{\mathit{j}}_{\mathbf{1}},\mathbf{1}),{\mathit{j}}_{\mathbf{1}}=\mathbf{1},\cdots ,\mathit{n}\rangle$, $\langle \mathit{a}(\mathit{n},\mathbf{1},{\mathit{k}}_{\mathbf{1}}),{\mathit{k}}_{\mathbf{1}}=\mathbf{1},\cdots ,\mathit{n}\rangle$, $\langle \mathit{a}({\mathit{i}}_{\mathbf{1}},\mathbf{1},\mathit{n}),{\mathit{i}}_{\mathbf{1}}=\mathbf{1},\cdots ,\mathit{n}\rangle$, $\langle \mathit{a}(\mathbf{1},{\mathit{j}}_{\mathbf{2}},\mathit{n}),{\mathit{j}}_{\mathbf{2}}=\mathbf{1},\cdots ,\mathit{n}\rangle$, $\langle \mathit{a}(\mathbf{1},\mathit{n},{\mathit{k}}_{\mathbf{2}}),{\mathit{k}}_{\mathbf{2}}=\mathbf{1},\cdots ,\mathit{n}\rangle$ and $\langle \mathit{a}({\mathit{i}}_{\mathbf{2}},\mathit{n},\mathbf{1}),{\mathit{i}}_{\mathbf{2}}=\mathbf{1},\cdots ,\mathit{n}\rangle$, respectively.

The binary searches along these paths identify indexes ${\mathit{j}}_{\mathbf{1}}$, ${\mathit{k}}_{\mathbf{1}}$, ${\mathit{i}}_{\mathbf{1}}$, ${\mathit{j}}_{\mathbf{2}}$, ${\mathit{k}}_{\mathbf{2}}$ and ${\mathit{i}}_{\mathbf{2}}$, respectively, such that $\mathit{x}>{\mathit{v}}^{\prime }$, $\forall {\mathit{v}}^{\prime }\in \{\mathit{a}({\mathit{i}}_{\mathbf{1}},\mathit{n},\mathbf{1}),\mathit{a}({\mathit{i}}_{\mathbf{2}},\mathbf{1},\mathit{n}),\mathit{a}(\mathbf{1},{\mathit{j}}_{\mathbf{1}},\mathit{n}),\mathit{a}(\mathit{n},{\mathit{j}}_{\mathbf{2}},\mathbf{1}),\mathit{a}(\mathbf{1},\mathit{n},{\mathit{k}}_{\mathbf{1}}),\mathit{a}(\mathit{n},\mathbf{1},{\mathit{k}}_{\mathbf{2}})\}$ and $\mathit{x}<{\mathit{v}}^{″}$, $\forall {\mathit{v}}^{″}\in \{\mathit{a}({\mathit{i}}_{\mathbf{1}}+\mathbf{1},\mathit{n},\mathbf{1}),\mathit{a}({\mathit{i}}_{\mathbf{2}}+\mathbf{1},\mathbf{1},\mathit{n}),\mathit{a}(\mathbf{1},{\mathit{j}}_{\mathbf{1}}+\mathbf{1},\mathit{n}),\mathit{a}(\mathit{n},{\mathit{j}}_{\mathbf{2}}+\mathbf{1},\mathbf{1}),\mathit{a}(\mathbf{1},\mathit{n},{\mathit{k}}_{\mathbf{1}}+\mathbf{1}),\mathit{a}(\mathit{n},\mathbf{1},{\mathit{k}}_{\mathbf{2}}+\mathbf{1})\}$. The index ${\mathit{j}}_{\mathbf{1}}$ allows to discard the two-dimensional subarrays $\mathit{a}((\mathbf{1},\mathbf{1},\mathbf{1}),\cdots ,(\mathit{n},{\mathit{j}}_{\mathbf{1}},\mathbf{1}))$ and $\mathit{a}((\mathit{n},{\mathit{i}}_{\mathbf{1}}+\mathbf{1},\mathbf{1}),\cdots ,(\mathit{n},\mathit{n},\mathit{n}))$. The subarrays discarded via index ${\mathit{i}}_{\mathbf{2}}$ are $\mathit{A}((\mathbf{1},\mathbf{1},\mathbf{1}),\cdots ,({\mathit{i}}_{\mathbf{2}},\mathit{n},\mathbf{1}))$ and $\mathit{A}(({\mathit{i}}_{\mathbf{2}}+\mathbf{1},\mathit{n},\mathbf{1}),\cdots ,(\mathit{n},\mathit{n},\mathit{n}))$, as depicted in the Figure 6b. Each of the other indices, similarly, allows two other two-dimensional subarrays to be discarded.

However, in the worst case, there may remain a subarray of each of the original six faces of $\mathit{A}$. For example, regarding the indices ${\mathit{j}}_{\mathbf{1}}$ and ${\mathit{i}}_{\mathbf{2}}$, there remains the subarray $\mathit{A}(({\mathit{i}}_{\mathbf{2}},{\mathit{j}}_{\mathbf{1}},\mathbf{1}),\cdots ,(\mathit{n},\mathit{n},\mathbf{1}))$ within the original face $\mathit{A}\left(\right(\mathbf{1},\mathbf{1},\mathbf{1}),\cdots ,(\mathit{n},\mathit{n},\mathbf{1}\left)\right)$, as depicted in the Figure 6b. In the second stage, the L&S algorithm searches for $\mathit{x}$ in these six subarrays using the adaption of saddleback search for the rectangle. In the worst case, when $\mathit{x}$ is not found by any of these searches, what is left of the original array $\mathit{A}$ is a subarray of dimension $(\mathit{n}-\mathbf{2})\times (\mathit{n}-\mathbf{2})\times (\mathit{n}-\mathbf{2})$, to which the algorithm L&S is again applied.

The pseudocode of the L&S algorithm is given in Algorithm 10. The specialized version of the binary search in steps 8 to 13 return both an indication of whether the key was found (or not) and its position in the array (or the position of the first entry greater than the key). The operator ∨ in steps 9 to 13 implies that the algorithm is terminated if one of the binary searches along the YBR path finds $\mathit{x}$. Similarly, in steps 15 to 20, the search is terminated if one of the calls to the specialized version of the saddleback search finds $\mathit{x}$.

It is straightforward to show that the L&S algorithm has the following recurrence for the worst-case number of required comparisons needed to search for a key $\mathit{x}$:

$$\mathbf{\tau }(\mathit{n},\mathbf{3})⩽\mathbf{\tau }(\mathit{n}-\mathbf{2},\mathbf{3})+\mathbf{6}lg(\mathit{n}+\mathbf{1})+\mathbf{6}(\mathit{n}-\mathbf{1}).$$

(30)

Solving the recurrence (30), establishes the following upper bound on the number of comparisons required by the L&S algorithm [5].

$$\mathbf{\tau }(\mathit{n},\mathbf{3})⩽\mathbf{3}{\mathit{n}}^{\mathbf{2}}/\mathbf{2}+\mathbf{3}\mathit{n}lg(\mathit{n}+\mathbf{2}).$$

(31)

Algorithm 10 L&S$(\mathit{A},\mathit{x})$

Input: Array $\mathit{A}(({\ell }_{\mathbf{1}},{\ell }_{\mathbf{2}},{\ell }_{\mathbf{3}}),\cdots ,({\mathit{r}}_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}}))$ and key $\mathit{x}\in \mathbb{R}$.

Output: True if $\mathit{x}\in \mathit{A}$ or False otherwise.

1. if $({\ell }_{\mathbf{1}}={\mathit{r}}_{\mathbf{1}})$ and $(\mathit{a}({\ell }_{\mathbf{1}},{\ell }_{\mathbf{2}},{\ell }_{\mathbf{3}})=\mathit{x})$ then                   // Stop conditions

2.    return true

3. end if

4. if$({\ell }_{\mathbf{1}}={\mathit{r}}_{\mathbf{1}})$ and $(\mathit{a}({\ell }_{\mathbf{1}},{\ell }_{\mathbf{2}},{\ell }_{\mathbf{3}})\ne \mathit{x})$then

5.    return false.

6. end if

7. $\mathit{found}\leftarrow$ false;                        // Stage 1: Search on YBR path.

8. $({\mathit{i}}_{\mathbf{1}},\mathit{found})\leftarrow$ BinarySearch($\mathit{A}(({\ell }_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\ell }_{\mathbf{3}}),\cdots ,({\mathit{r}}_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\ell }_{\mathbf{3}})),\mathit{x}$);

9. $({\mathit{k}}_{\mathbf{1}},\mathit{found})\leftarrow \mathit{found}\vee$ BinarySearch($\mathit{A}(({\ell }_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\ell }_{\mathbf{3}}),\cdots ,({\ell }_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}})),\mathit{x}$);

10. $({\mathit{j}}_{\mathbf{1}},\mathit{found})\leftarrow \mathit{found}\vee$ BinarySearch($\mathit{A}(({\ell }_{\mathbf{1}},{\ell }_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}}),\cdots ,({\ell }_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}})),\mathit{x}$);

11. $({\mathit{i}}_{\mathbf{2}},\mathit{found})\leftarrow \mathit{found}\vee$ BinarySearch($\mathit{A}(({\ell }_{\mathbf{1}},{\ell }_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}}),\cdots ,({\mathit{r}}_{\mathbf{1}},{\ell }_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}})),\mathit{x}$);

12. $({\mathit{k}}_{\mathbf{2}},\mathit{found})\leftarrow \mathit{found}\vee$ BinarySearch($\mathit{A}(({\mathit{r}}_{\mathbf{1}},{\ell }_{\mathbf{2}},{\ell }_{\mathbf{3}}),\cdots ,({\mathit{r}}_{\mathbf{1}},{\ell }_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}})),\mathit{x}$);

13. $({\mathit{j}}_{\mathbf{2}},\mathit{found})\leftarrow \mathit{found}\vee$ BinarySearch($\mathit{A}(({\mathit{r}}_{\mathbf{1}},{\ell }_{\mathbf{2}},{\ell }_{\mathbf{3}}),\cdots ,({\mathit{r}}_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\ell }_{\mathbf{3}})),\mathit{x}$);

14. if not $\mathit{found}$ then                      // Stage 2: Search on A sub-faces.

15.    $\mathit{found}\leftarrow$ SaddlebackSearch($\mathit{A}(({\mathit{i}}_{\mathbf{1}},{\mathit{j}}_{\mathbf{2}},{\ell }_{\mathbf{3}}),\cdots ,({\mathit{r}}_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\ell }_{\mathbf{3}})),\mathit{x}$);

16.    $\mathit{found}\leftarrow \mathit{found}\vee$ SaddlebackSearch($\mathit{A}(({\ell }_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\ell }_{\mathbf{1}}),\cdots ,({\mathit{i}}_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\mathit{k}}_{\mathbf{1}})),\mathit{x}$);

17.    $\mathit{found}\leftarrow \mathit{found}\vee$ SaddlebackSearch($\mathit{A}(({\ell }_{\mathbf{1}},{\mathit{j}}_{\mathbf{1}},{\mathit{k}}_{\mathbf{1}}),\cdots ,({\ell }_{\mathbf{1}},{\mathit{r}}_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}})),\mathit{x}$);

18.    $\mathit{found}\leftarrow \mathit{found}\vee$ SaddlebackSearch($\mathit{A}(({\ell }_{\mathbf{1}},{\ell }_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}}),\cdots ,({\mathit{i}}_{\mathbf{2}},{\mathit{j}}_{\mathbf{1}},{\mathit{r}}_{\mathbf{3}})),\mathit{x}$);

19.    $\mathit{found}\leftarrow \mathit{found}\vee$ SaddlebackSearch($\mathit{A}(({\mathit{i}}_{\mathbf{2}},{\ell }_{\mathbf{2}},{\mathit{k}}_{\mathbf{2}}),\cdots ,({\mathit{r}}_{\mathbf{1}},{\ell }_{\mathbf{2}},{\mathit{r}}_{\mathbf{3}})),\mathit{x}$);

20.    $\mathit{found}\leftarrow \mathit{found}\vee$ SaddlebackSearch($\mathit{A}(({\mathit{r}}_{\mathbf{1}},{\ell }_{\mathbf{2}},{\ell }_{\mathbf{3}}),\cdots ,({\mathit{r}}_{\mathbf{3}},{\mathit{j}}_{\mathbf{2}},{\mathit{k}}_{\mathbf{2}})),\mathit{x}$);

21. end if

22. if not $\mathit{found}$ then                       // Recursive call of L&S algorithm.

23.      $\mathit{found}\leftarrow$ L&S($\mathit{A}(({\ell }_{\mathbf{1}}+\mathbf{1},{\ell }_{\mathbf{2}}+\mathbf{1},{\ell }_{\mathbf{3}}+\mathbf{1}),\cdots ,({\mathit{r}}_{\mathbf{1}}-\mathbf{1},{\mathit{r}}_{\mathbf{2}}-\mathbf{1},{\mathit{r}}_{\mathbf{3}}-\mathbf{1})),\mathit{x}$);

24. end if

25. return$\mathit{found}$.

While the L&S algorithm is worst-case optimal, for small arrays it does not necessarily have the best performance. The approach, denoted here by SBS3, is based on partitioning $\mathit{A}$ into $\mathit{n}$ isomorphic copies of its 2-dimensional subarrays, each consisting of all entries that have identical 3^rd coordinates. Saddleback search is then used repeatedly to search each 2-dimensional subarray. SBS3 has worst case time complexity of $\mathbf{\tau }(\mathit{n},\mathbf{3})⩽\mathbf{2}{\mathit{n}}^{\mathbf{2}}-\mathit{n}$. This complexity is compared with that of the L&S algorithm $\mathbf{\tau }(\mathit{n},\mathbf{3})⩽(\mathbf{3}\mathit{n}/\mathbf{2}+\mathbf{3}\mathit{n}lg(\mathit{n}+\mathbf{2}\left)\right)$ in Figure 7. It can be seen that SBS3 is superior when $\mathit{n}⩽\mathbf{33}$ and the L&S algorithm dominates otherwise.

5.2. The Unbalanced Case (the Cuboid)

Of course, the unbalanced 3-dimensional array, the cuboid, is a special case of the hypercuboid. As given in (37) below, Linial and Saks (Theorem 5.3 in [5]) showed that for ${\mathit{n}}_{\mathbf{1}}⩾{\mathit{n}}_{\mathbf{2}}⩾\cdots ⩾{\mathit{n}}_{\mathit{d}}$; the performance $\mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},\dots ,{\mathit{n}}_{\mathit{d}})$ of any search algorithm of the rectangular hypercuboid is bounded above and below by functions of the order of $\mathcal{O}({\mathit{n}}_{\mathbf{1}}\cdots {\mathit{n}}_{\mathit{d}}lg\left(\lceil {\mathit{n}}_{\mathbf{1}}/{\mathit{n}}_{\mathbf{2}}\rceil \right)$).

Furthermore, it is possible to extend to cuboids, the search methods for unbalanced 2-arrays of Shen [8] and Bird [7] given in Section 4. For example, such an algorithm extended from one of the Shen’s methods iteratively searches particular cuboids of smaller sizes after discarding entries of the original cuboid $\mathit{A}$ that cannot be $\mathit{x}$ [33]. The algorithm identifies a pivot (the maximum entry that is less than or equal to the key $\mathit{x}$) by applying binary search to a particular diagonal of the middle (balanced) 3-dimensional array of maximum possible volume of the current cuboid. Once found, the pivot is used to discard entries of $\mathit{A}$, if possible, using (1) and (3). The remainder of the cuboid is then divided into three smaller cuboids ${\mathit{A}}_{\mathbf{1}}$, ${\mathit{A}}_{\mathbf{2}}$ and ${\mathit{A}}_{\mathbf{3}}$ (see Figure 8).

The same process is repeated on these three smaller cuboids, until either $\mathit{x}$ is found or all of the remaining cuboids are one- or two-dimensional subarrays. Binary search is used to explore any remaining vectors and either Bird’s or Shen’s method [7,8] is used for any remaining two-dimensional subarrays. This leads to the recurrence (32), given next. The attainment of exact bounds derived from (32) remains an open problem.

$$\mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}},{\mathit{n}}_{\mathbf{3}})=\left\{\begin{array}{cc}\mathbf{1},\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{1}}={\mathit{n}}_{\mathbf{2}}={\mathit{n}}_{\mathbf{3}}=\mathbf{1};\hfill \\ lg({\mathit{n}}_{\mathbf{1}}+\mathbf{1}),\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{1}}>\mathbf{1}\mathrm{and}{\mathit{n}}_{\mathbf{2}}={\mathit{n}}_{\mathbf{3}}=\mathbf{1};\hfill \\ lg({\mathit{n}}_{\mathbf{2}}+\mathbf{1}),\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{2}}>\mathbf{1}\mathrm{and}{\mathit{n}}_{\mathbf{1}}={\mathit{n}}_{\mathbf{3}}=\mathbf{1};\hfill \\ lg({\mathit{n}}_{\mathbf{3}}+\mathbf{1}),\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{3}}>\mathbf{1}\mathrm{and}{\mathit{n}}_{\mathbf{1}}={\mathit{n}}_{\mathbf{2}}=\mathbf{1};\hfill \\ \mathcal{O}(min\{{\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}}\}lg(\frac{max\{{\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}}\}}{min\{{\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}}\}}+\mathbf{1})),\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}}>\mathbf{1}\mathrm{and}{\mathit{n}}_{\mathbf{3}}=\mathbf{1};\hfill \\ \mathcal{O}(min\{{\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{3}}\}lg(\frac{max\{{\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{3}}\}}{min\{{\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{3}}\}}+\mathbf{1})),\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{3}}>\mathbf{1}\mathrm{and}{\mathit{n}}_{\mathbf{2}}=\mathbf{1};\hfill \\ \mathcal{O}(min\{{\mathit{n}}_{\mathbf{2}},{\mathit{n}}_{\mathbf{3}}\}lg(\frac{max\{{\mathit{n}}_{\mathbf{2}},{\mathit{n}}_{\mathbf{3}}\}}{min\{{\mathit{n}}_{\mathbf{2}},{\mathit{n}}_{\mathbf{3}}\}}+\mathbf{1})),\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{2}},{\mathit{n}}_{\mathbf{3}}>\mathbf{1}\mathrm{and}{\mathit{n}}_{\mathbf{1}}=\mathbf{1};\hfill \\ \mathcal{O}(lg(max\{{\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}},{\mathit{n}}_{\mathbf{3}}\}+\mathbf{1})+\hfill \\ \mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},\lceil {\mathit{n}}_{\mathbf{2}}/\mathbf{2}\rceil ,\lfloor {\mathit{n}}_{\mathbf{3}}/\mathbf{2}\rfloor )+\hfill & \\ \mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rfloor ,{\mathit{n}}_{\mathbf{2}},\lceil {\mathit{n}}_{\mathbf{3}}/\mathbf{2}\rceil )+\hfill & \\ \mathbf{\varphi }(\lceil {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rceil ,\lfloor {\mathit{n}}_{\mathbf{2}}/\mathbf{2}\rfloor ,{\mathit{n}}_{\mathbf{3}}),\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(32)

6. Searching in Higher Dimensions $(\mathit{d}⩾\mathbf{4})$

6.1. Balanced Case (Hypercubes)

Cheng et al [9] extended the results of Linial and Saks [5] for the cube, described in Section 5, to $\mathit{d}$-dimensional hypercubes for $\mathit{d}⩾\mathbf{4}$. The Cheng et al. algorithm is described as a generalization of a particular algorithm (which we call Cheng-4) for the special case $\mathit{d}=\mathbf{4}$. The authors use the lower bound $\mathbf{4}/\mathbf{3}{\mathit{n}}^{\mathbf{3}}-\mathit{n}/\mathbf{3}⩽\mathbf{\tau }(\mathit{n},\mathbf{4})$ to the Cheng-4 algorithm, which they showed to be asymptotically tight.

Cheng-4 first selects eight particular 2-$\mathit{d}$ outer faces of the 4-$\mathit{d}$ hypercube $\mathit{A}$ and uses an adaptation of the saddleback search to partition each of these eight 2-$\mathit{d}$ arrays into two surfaces, requiring at most $\mathbf{8}(\mathbf{2}\mathit{n}-\mathbf{1})$ tests. These surfaces generate eight 3-$\mathit{d}$ subarrays of $\mathit{A}$ that are then searched with at most $\mathbf{8}{\mathit{n}}^{\mathbf{2}}$ tests. Similarly to the L&S algorithm this process reduces the remaining 4-$\mathit{d}$ hypercube to be searched to one with sizes $(\mathit{n}-\mathbf{2})$. The authors established that, for $\mathit{n}>\mathbf{2}$, the worst case performance of their algorithm is given by

$$\mathbf{\tau }(\mathit{n},\mathbf{4})⩽\mathbf{\tau }(\mathit{n}-\mathbf{2},\mathbf{4})+\mathbf{8}{\mathit{n}}^{\mathbf{2}}+\mathbf{8}(\mathbf{2}\mathit{n}-\mathbf{1}).$$

(33)

This recurrence implies that $\mathbf{\tau }(\mathit{n},\mathbf{4})⩽\mathbf{4}/\mathbf{3}{\mathit{n}}^{\mathbf{3}}+\mathcal{O}\left({\mathit{n}}^{\mathbf{2}}\right)$. Therefore, using their lower bound the authors have shown that

$$\mathbf{4}/\mathbf{3}{\mathit{n}}^{\mathbf{3}}-\mathit{n}/\mathbf{3}⩽\mathbf{\tau }(\mathit{n},\mathbf{4})⩽\mathbf{4}/\mathbf{3}{\mathit{n}}^{\mathbf{3}}+\mathcal{O}\left({\mathit{n}}^{\mathbf{2}}\right),$$

(34)

and that the algorithm is asymptotically optimal up to the lower order terms.

The partition of each one of the eight 2-$\mathit{d}$ outer faces of the 4-$\mathit{d}$ hypercube generates two subsets $\mathit{S}$ and $\mathit{L}$, such that $\mathit{S}$ contains entries smaller than $\mathit{x}$ and $\mathit{L}$ contains entries larger than $\mathit{x}$. These subsets are derived from two 2-dimensional arrays $\mathit{u}$ and $\mathit{v}$, each containing $\mathit{n}$ integers such that ${\mathit{i}}_{\mathbf{1}}⩽\mathit{u}\left[{\mathit{i}}_{\mathbf{2}}\right]$ iff $\mathit{a}({\mathit{i}}_{\mathbf{1}},{\mathit{i}}_{\mathbf{2}})<\mathit{x}$ and ${\mathit{i}}_{\mathbf{2}}⩽\mathit{v}\left[{\mathit{i}}_{\mathbf{1}}\right]$ iff $\mathit{a}({\mathit{i}}_{\mathbf{1}},{\mathit{i}}_{\mathbf{2}})<\mathit{x}$. The sets $\mathit{S}$ and $\mathit{L}$, as well as the arrays $\mathit{u}$ and $\mathit{v}$ are illustrated in Figure 9.

The eight 2-$\mathit{d}$ outer faces are defined by fixing a pair of subscripts $({\mathit{i}}_{\mathit{p}},{\mathit{i}}_{\mathit{q}})$, $\mathit{p}=\mathbf{1},\cdots ,\mathbf{4}$ and $\mathit{q}=(\mathit{p}+\mathbf{1})mod\mathbf{4}$, to either $(\mathbf{1},\mathit{n})$ or $(\mathit{n},\mathbf{1})$ and are denoted by ${\mathit{M}}_{\mathbf{i}}$ and ${\mathit{M}}_{\mathbf{i}}^{*}$, $\mathit{i}=\mathbf{1},\cdots ,\mathbf{4}$. For example, ${\mathit{M}}_{\mathbf{1}}$ is obtained by the indexes $\mathit{a}({\mathit{i}}_{\mathbf{1}},{\mathit{i}}_{\mathbf{2}},\mathbf{1},\mathit{n})$, ${\mathit{i}}_{\mathbf{1}},{\mathit{i}}_{\mathbf{2}}=\mathbf{1},\cdots ,\mathit{n}$, and generates the partitions ${\mathit{S}}_{\mathbf{1}}$ and ${\mathit{L}}_{\mathbf{1}}$. Similarly, ${\mathit{M}}_{\mathbf{1}}^{*}=\left\{\mathit{a}({\mathit{i}}_{\mathbf{1}},{\mathit{i}}_{\mathbf{2}},\mathit{n},\mathbf{1})\right\}$, ${\mathit{i}}_{\mathbf{1}},{\mathit{i}}_{\mathbf{2}}=\mathbf{1},\cdots ,\mathit{n}$, generates ${\mathit{S}}_{\mathbf{1}}^{*}$ and ${\mathit{L}}_{\mathbf{1}}^{*}$.

Using some properties as to whether or not the key belongs to the 2-$\mathit{d}$ partitions, eight 3-$\mathit{d}$ surfaces ${\mathit{Q}}_{\mathit{i}}=\left\{\mathit{a}({\mathit{i}}_{\mathbf{1}},{\mathit{i}}_{\mathbf{2}},{\mathit{i}}_{\mathbf{3}},{\mathit{i}}_{\mathbf{4}})\right\}$ and ${\mathit{Q}}_{\mathit{i}}^{*}=\left\{\mathit{a}({\mathit{j}}_{\mathbf{1}},{\mathit{j}}_{\mathbf{2}},{\mathit{j}}_{\mathbf{3}},{\mathit{j}}_{\mathbf{4}})\right\}$ are defined, by fixing ${\mathit{i}}_{\mathit{k}}=\mathbf{1}$ and ${\mathit{j}}_{\mathit{k}}=\mathit{n}$ for $\mathit{k}=\mathbf{1},\cdots ,\mathbf{4}$. The search then proceeds in some subarrays of these eight surfaces generated by the intersections induced by the partitions ${\mathit{S}}_{\mathit{i}}$ and ${\mathit{L}}_{\mathit{i}}$ (${\mathit{S}}_{\mathit{i}}^{*}$ and ${\mathit{L}}_{\mathit{i}}^{*}$). An example of these intersections is depicted in Figure 10. For further details the reader is referred to [9].

Cheng et al. [9] also showed how the algorithm Cheng-4 can be generalised to $\mathit{d}$-dimensional hypercubes, for $\mathit{d}⩾\mathbf{5}$, in a straightforward way. As with Cheng-4, the search is carried out in two steps. In the first step, the algorithm partitions the original matrix ${\mathit{A}}_{\mathit{n},\mathit{d}}$ into $\mathbf{2}\mathit{d}$ subsets ${\mathit{S}}_{\mathit{k}}$ and ${\mathit{L}}_{\mathit{k}}$, $\mathit{k}=\mathbf{1},\cdots ,\mathit{d}$; such that ${\mathit{S}}_{\mathit{k}}$ contains entries smaller than $\mathit{x}$ and ${\mathit{L}}_{\mathit{k}}$ contains entries larger than $\mathit{x}$. The algorithm considers $\mathbf{2}\mathit{d}$$(\mathit{d}-\mathbf{2})$-dimensional arrays as defined below:

$$\begin{array}{c}\hfill {\mathit{M}}_{\mathit{k}}=\{\mathit{a}({\mathit{i}}_{\mathbf{1}},{\mathit{i}}_{\mathbf{2}},\cdots ,{\mathit{i}}_{\mathit{d}})\mid {\mathit{i}}_{\mathit{k}-\mathbf{2}}=\mathbf{1},{\mathit{i}}_{\mathit{k}-\mathbf{1}}=\mathit{n}\}\Rightarrow {\mathit{S}}_{\mathit{k}},{\mathit{L}}_{\mathit{k}},\\ \hfill {\mathit{M}}_{\mathit{k}}^{*}=\{\mathit{a}({\mathit{i}}_{\mathbf{1}},{\mathit{i}}_{\mathbf{2}},\cdots ,{\mathit{i}}_{\mathit{d}})\mid {\mathit{i}}_{\mathit{k}-\mathbf{2}}=\mathit{n},{\mathit{i}}_{\mathit{k}-\mathbf{1}}=\mathbf{1}\}\Rightarrow {\mathit{S}}_{\mathit{k}}^{*},{\mathit{L}}_{\mathit{k}}^{*}.\end{array}$$

The aim of using the subsets ${\mathit{S}}_{\mathit{k}}$ and ${\mathit{L}}_{\mathit{k}}$ is to attempt to eliminate part of the surface of a particular subarray by fixing $(\mathit{d}-\mathbf{3})$ subscripts.

The $\mathit{d}$ pairs of “mutually complementary” subsets (${\mathit{S}}_{\mathit{k}}$, ${\mathit{L}}_{\mathit{k}}$) and (${\mathit{S}}_{\mathit{k}}^{*}$, ${\mathit{L}}_{\mathit{k}}^{*}$) ($\mathit{k}=\mathbf{1},\cdots ,\mathit{d}$) have the following properties:

(a)

$\mathit{x}>\mathit{a}({\mathit{i}}_{\mathbf{1}},\cdots ,{\mathit{i}}_{\mathit{d}}\mid {\mathit{i}}_{(\mathit{k}-\mathbf{2})mod\mathit{d}}=\mathbf{1},{\mathit{i}}_{(\mathit{k}-\mathbf{1})mod\mathit{d}}=\mathit{n})$ and $\mathit{x}<\mathit{a}({\mathit{j}}_{\mathbf{1}},\cdots ,{\mathit{j}}_{\mathit{d}})\mid {\mathit{j}}_{(\mathit{k}-\mathbf{2})mod\mathit{d}}=\mathbf{1},{\mathit{j}}_{(\mathit{k}-\mathbf{1})mod\mathit{d}}=\mathit{n})$ for $({\mathit{i}}_{\mathit{k}},\cdots ,{\mathit{i}}_{\mathit{k}+\mathit{d}-\mathbf{3}})\in {\mathit{S}}_{\mathit{k}}$ and $({\mathit{j}}_{\mathit{k}},\cdots ,{\mathit{j}}_{\mathit{k}+\mathit{d}-\mathbf{3}})\in {\mathit{L}}_{\mathit{k}},$

(b)

$\mathit{x}>\mathit{a}({\mathit{i}}_{\mathbf{1}},\cdots ,{\mathit{i}}_{\mathit{d}}\mid {\mathit{i}}_{(\mathit{k}-\mathbf{2})mod\mathit{d}}=\mathit{n},{\mathit{i}}_{(\mathit{k}-\mathbf{1})mod\mathit{d}}=\mathbf{1})$ and $\mathit{x}<\mathit{a}({\mathit{j}}_{\mathbf{1}},\cdots ,{\mathit{j}}_{\mathit{d}})\mid {\mathit{j}}_{(\mathit{k}-\mathbf{2})mod\mathit{d}}=\mathit{n},{\mathit{j}}_{(\mathit{k}-\mathbf{1})mod\mathit{d}}=\mathbf{1})$ for $({\mathit{i}}_{\mathit{k}},\cdots ,{\mathit{i}}_{\mathit{k}+\mathit{d}-\mathbf{3}})\in {\mathit{S}}_{\mathit{k}}^{*}$ and $({\mathit{j}}_{\mathit{k}},\cdots ,{\mathit{j}}_{\mathit{k}+\mathit{d}-\mathit{3}})\in {\mathit{L}}_{\mathit{k}}^{*},$

for all $\mathit{k}=\mathbf{1},\cdots ,\mathit{d}$.

In total, the first step produces $\mathbf{4}\mathit{d}$$(\mathit{d}-\mathbf{3})$-dimensional arrays. At most $\mathbf{2}\mathit{n}-\mathbf{1}$ comparisons are needed for each fixed subscript ${\mathit{i}}_{\mathbf{2}},\cdots ,{\mathit{i}}_{\mathit{d}-\mathbf{3}}$ and hence at most $\mathbf{2}{\mathit{dn}}^{\mathit{d}-\mathbf{4}}(\mathbf{2}\mathit{n}-\mathbf{1})$ comparisons in total are required.

In the second step, the surfaces of the subarrays are searched in order to reduce the region of uncertainty to a $\mathit{d}$-dimensional array with sizes at most $(\mathit{n}-\mathbf{2})$. The algorithm searches the following $\mathbf{2}\mathit{d}$$(\mathit{d}-\mathbf{1})$-dimensional surfaces of ${\mathit{A}}_{\mathit{n},\mathit{d}}$, that are defined by fixing one of the subscripts at either 1 or $\mathit{n}$:

$$\begin{array}{cc}\hfill {\mathit{Q}}_{\mathit{k}}& =\{\mathit{a}({\mathit{i}}_{\mathbf{1}},\cdots ,{\mathit{i}}_{\mathit{d}})\mid {\mathit{i}}_{\mathit{k}}=\mathbf{1}\},\hfill \\ \hfill {\mathit{Q}}_{\mathit{k}}^{*}& =\{\mathit{a}({\mathit{i}}_{\mathbf{1}},\cdots ,{\mathit{i}}_{\mathit{d}})\mid {\mathit{i}}_{\mathit{k}}=\mathit{n}\},\hfill \\ \hfill \mathit{k}& =\mathbf{1},\cdots ,\mathit{d}.\hfill \end{array}$$

In total, the second step requires at most $\mathbf{2}{\mathit{dn}}^{\mathit{d}-\mathbf{2}}$ comparisons.

Steps 1 and 2 reduce the original array to a $\mathit{d}$-dimensional array ${\mathit{A}}_{\mathit{n}-\mathbf{2},\mathit{d}}$, with sizes of at most $(\mathit{n}-\mathbf{2})$. That is,

$${\mathit{A}}_{\mathit{n}-\mathbf{2},\mathit{d}}=\{{\mathit{a}}_{{\mathit{i}}_{\mathbf{1}},\cdots ,{\mathit{i}}_{\mathit{d}}}\mid {\mathit{i}}_{\mathit{1}},\cdots ,{\mathit{i}}_{\mathit{d}}=\mathbf{2},\cdots ,\mathit{n}-\mathbf{1}\}.$$

Hence the generalised recursion is:

$$\mathbf{\tau }(\mathit{n},\mathit{d})⩽\left\{\begin{array}{cc}\mathbf{1},\hfill & \mathrm{if}\mathit{n}=\mathbf{1};\hfill \\ \mathbf{2}\mathit{d},\hfill & \mathrm{if}\mathit{n}=\mathbf{2};\hfill \\ \mathbf{\tau }(\mathit{n}-\mathbf{2},\mathit{d})+\mathbf{2}{\mathit{dn}}^{\mathit{d}-\mathbf{2}}+\mathbf{2}{\mathit{dn}}^{\mathit{d}-\mathbf{4}}(\mathbf{2}\mathit{n}-\mathbf{1}),\hfill & \mathrm{for}\mathit{n}>\mathbf{2}.\hfill \end{array}\right.$$

(35)

Solving this recursion leads to a worst case performance of the algorithm of

$$\mathbf{\tau }(\mathit{n},\mathit{d})⩽\left(\frac{\mathit{d}}{\mathit{d}-\mathbf{1}}\right){\mathit{n}}^{\mathit{d}-\mathbf{1}}+\mathcal{O}\left({\mathit{n}}^{\mathit{d}-\mathbf{2}}\right),\mathit{d}⩾\mathbf{4}.$$

(36)

6.2. Unbalanced Case (the Hypercuboids)

For the general case of a $\mathit{d}$-dimensional array that is not necessarily balanced, Linial and Saks [5] proved that, for ${\mathit{n}}_{\mathbf{1}}⩾{\mathit{n}}_{\mathbf{2}}⩾\cdots ⩾{\mathit{n}}_{\mathit{d}}$; there exists a nonincreasing function ${\mathit{k}}_{\mathbf{1}}\left(\mathit{d}\right)$ and a function ${\mathit{k}}_{\mathbf{2}}\left(\mathit{d}\right)$ such that the performance $\mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},\cdots ,{\mathit{n}}_{\mathit{d}})$ of any search algorithm is bounded as follows:

$${\mathit{k}}_{\mathbf{2}}\left(\mathit{d}\right){\mathit{n}}_{\mathbf{1}}\cdots {\mathit{n}}_{\mathit{d}-\mathbf{1}}lg(\frac{{\mathit{n}}_{\mathit{d}}}{{\mathit{n}}_{\mathit{d}-\mathbf{1}}}+\mathbf{1})⩽\mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},\cdots ,{\mathit{n}}_{\mathit{d}})⩽{\mathit{k}}_{\mathbf{1}}\left(\mathit{d}\right){\mathit{n}}_{\mathbf{1}}\cdots {\mathit{n}}_{\mathit{d}-\mathbf{2}}lg(\frac{{\mathit{n}}_{\mathit{d}}}{{\mathit{n}}_{\mathit{d}-\mathbf{1}}}+\mathbf{1}),$$

(37)

7. The Worst Case Performance of Some of the Revised Algorithms

From (8), the binary search of a sorted one-dimensional array of size $\mathit{n}$ can be performed with $\lfloor log\left(\mathit{n}\right)\rfloor +\mathbf{1}$ comparisons in the worst case. However, there is some justification in assuming that using (1), (2) and (3) at each iteration of such a binary search actually requires two comparisons (not one). Some implications of making such an assumption are now established.

7.1. Binary and $\mathit{k}$-Nary Search Revised

The worst case performance of the binary search version that uses only one comparison at each iteration, as described in Section 3, can be stated as follows:

$$\mathbf{\tau }(\mathit{n},\mathbf{1})⩽\left\{\begin{array}{cc}\mathbf{1},\hfill & \mathrm{if}\mathit{n}=\mathbf{1};\hfill \\ \mathbf{1}+\mathbf{\tau }(\lfloor \mathit{n}/\mathbf{2}\rfloor ,\mathbf{1}),\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(38)

Therefore,

$$\begin{array}{cc}\hfill \mathbf{\tau }(\mathit{n},\mathbf{1})& ⩽\mathbf{1}+\mathbf{\tau }(\lfloor \mathit{n}/\mathbf{2}\rfloor ,\mathbf{1})\hfill \\ \hfill & =\mathbf{1}+\mathbf{1}+\mathbf{\tau }(\lfloor \mathit{n}/\mathbf{2}\rfloor /\mathbf{2},\mathbf{1})\hfill \\ \hfill & ⋮\hfill \\ \hfill & =\underset{\mathit{i}}{\underbrace{\mathbf{1}+\cdots +\mathbf{1}}}+\mathbf{\tau }(\lfloor \mathit{n}/\mathbf{2}\rfloor /{\mathbf{2}}^{\mathit{i}-\mathbf{1}},\mathbf{1})\hfill \\ \hfill & =\underset{\mathbf{i}}{\underbrace{\mathbf{1}+\cdots +\mathbf{1}}}+\mathbf{\tau }(\lfloor \mathit{n}/{\mathbf{2}}^{\mathit{i}}\rfloor ,\mathbf{1})\hfill \\ \hfill & =\mathit{i}+\mathbf{\tau }(\lfloor \mathit{n}/{\mathbf{2}}^{\mathit{i}}\rfloor ,\mathbf{1}).\hfill \end{array}$$

When $\lfloor \mathit{n}/{\mathbf{2}}^{\mathit{i}}\rfloor =\mathbf{1}$, $\mathbf{\tau }(\lfloor \mathit{n}/{\mathbf{2}}^{\mathit{i}}\rfloor ,\mathbf{1})=\mathbf{\tau }(\mathbf{1},\mathbf{1})=\mathbf{1}$. Moreover,

$$\begin{array}{cc}\hfill \lfloor \mathit{n}/{\mathbf{2}}^{\mathit{i}}\rfloor =\mathbf{1}& \Rightarrow \mathbf{1}⩽\mathit{n}/{\mathbf{2}}^{\mathit{i}}<\mathbf{2}\hfill \\ \hfill & \Rightarrow {\mathbf{2}}^{\mathit{i}}⩽\mathit{n}<{\mathbf{2}}^{\mathit{i}+\mathbf{1}}\hfill \\ \hfill & \Rightarrow lg{\mathbf{2}}^{\mathit{i}}⩽lg\mathit{n}<lg{\mathbf{2}}^{\mathit{i}+\mathbf{1}}\hfill \\ \hfill & \Rightarrow \mathit{i}⩽lg\mathit{n}<\mathit{i}+\mathbf{1}\hfill \\ \hfill & \Rightarrow \mathit{i}=\lfloor lg\mathit{n}\rfloor .\hfill \end{array}$$

Thus,

$$\mathbf{\tau }(\mathit{n},\mathbf{1})⩽\lfloor lg\mathit{n}\rfloor +\mathbf{1}.$$

(39)

This result can be generalised to $\mathit{k}$-nary versions of the algorithm, i.e., that divide the search space into $\mathit{k}$ parts, as follows:

$$\mathbf{\tau }(\mathit{n},\mathbf{1})⩽\left\{\begin{array}{cc}{\mathit{c}}_{\mathit{k}},\hfill & \mathrm{if}\mathit{n}<\mathit{k};\hfill \\ {\mathit{b}}_{\mathit{k}}+\mathbf{\tau }(\lfloor \mathit{n}/\mathit{k}\rfloor ,\mathbf{1}),\hfill & \mathrm{otherwise};\hfill \end{array}\right.$$

(40)

where ${\mathit{c}}_{\mathit{k}}$ is a tight upper bound on the number of comparisons necessary to check the elements still eventually remaining after exiting the search loop and ${\mathit{b}}_{\mathit{k}}$ expresses the complexity of dividing the search space into $\mathit{k}$ parts, defined by $\mathit{k}-\mathbf{1}$ pivot elements, and the necessary comparisons of the key $\mathit{x}$ with those pivot elements. Thus,

$$\mathbf{\tau }(\mathit{n},\mathbf{1})⩽{\mathit{b}}_{\mathit{k}}\lfloor {log}_{\mathit{k}}\mathit{n}\rfloor +{\mathit{c}}_{\mathit{k}}.$$

(41)

Thus, as $\mathit{k}$ increases, the logarithm basis and the constants ${\mathit{c}}_{\mathit{k}}$ and ${\mathit{b}}_{\mathit{k}}$ also increase since more operations are necessary to determine in which subspace to continue the search. Therefore, in practice, the gain of performance obtained by increasing the logarithm basis is practically cancelled out by increasing the constants ${\mathit{c}}_{\mathit{k}}$ and ${\mathit{b}}_{\mathit{k}}$.

7.2. Shen’s Algorithm Revised

We now establish a revised exact count of the number of comparisons required by the Shen’s row search algorithm [8] in the worst case. The worst possible location of the pivot on the “middle” row of the matrix, discussed in Section 4.3, leads to the following revised recurrence relation for the algorithm:

$$\mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}})⩽\left\{\begin{array}{cc}\mathbf{1},\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{2}}={\mathit{n}}_{\mathbf{1}}=\mathbf{1};\hfill \\ \mathbf{2}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathbf{1},\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{2}}>\mathbf{1}\mathrm{and}{\mathit{n}}_{\mathbf{1}}=\mathbf{1};\hfill \\ \mathbf{2}\lfloor lg{\mathit{n}}_{\mathbf{1}}\rfloor +\mathbf{1},\hfill & \mathrm{if}{\mathit{n}}_{\mathbf{2}}=\mathbf{1}\mathrm{and}{\mathit{n}}_{\mathbf{1}}>\mathbf{1};\hfill \\ (\mathbf{2}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathbf{1})+\hfill \\ (\mathbf{2}\lfloor lg(\lceil {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rceil -\mathbf{1})\rfloor +\mathbf{1})+\hfill \\ \mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathbf{1}),\hfill & \mathrm{otherwise}.\hfill \end{array}\right.$$

(42)

Note ($\lfloor \mathit{x}\rfloor =\mathit{k}\iff \mathit{k}⩽\mathit{x}<\mathit{k}+\mathbf{1}$ and $\lceil \mathit{x}\rceil =\mathit{k}\iff \mathit{k}-\mathbf{1}<\mathit{x}⩽\mathit{k}$.) that $\lceil {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rceil -\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ⩽\mathbf{1}\Rightarrow \lceil {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rceil -\mathbf{1}⩽\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor$. Moreover, $\lfloor lg\lfloor {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rfloor \rfloor ⩽lg\lfloor {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rfloor$. Thus:

$$\begin{array}{cc}\hfill \mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}})& ⩽(\mathbf{2}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathbf{1})+(\mathbf{2}\lfloor lg(\lceil {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rceil -\mathbf{1})\rfloor +\mathbf{1})+\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathbf{1})\hfill \\ \hfill & ⩽(\mathbf{2}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathbf{1})+(\mathbf{2}lg\left(\lfloor {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rfloor \right)+\mathbf{1})+\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathbf{1})\hfill \\ \hfill & =[(\mathbf{2}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathbf{1})+(\mathbf{2}\lfloor lg({\mathit{n}}_{\mathbf{2}}-\mathbf{1})\rfloor +\mathbf{1})]+[(\mathbf{2}lg\left(\lfloor {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rfloor \right)+\mathbf{1})+\hfill \\ \hfill & (\mathbf{2}lg\left(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathbf{2}}\rfloor \right)+\mathbf{1})]+\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathbf{2}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathbf{2})\hfill \\ \hfill & ⋮\hfill \\ \hfill & =[(\mathbf{2}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathbf{1})+(\mathbf{2}\lfloor lg({\mathit{n}}_{\mathbf{2}}-\mathbf{1})\rfloor +\mathbf{1})+\cdots +(\mathbf{2}\lfloor lg({\mathit{n}}_{\mathbf{2}}-(\mathit{i}-\mathbf{1}))\rfloor +\mathbf{1})]+\hfill \\ \hfill & [(\mathbf{2}lg\left(\lfloor {\mathit{n}}_{\mathbf{1}}/\mathbf{2}\rfloor \right)+\mathbf{1})+(\mathbf{2}lg\left(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathbf{2}}\rfloor \right)+\mathbf{1})+\cdots +(\mathbf{2}lg\left(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor \right)+\mathbf{1})]+\hfill \\ \hfill & \mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathit{i}).\hfill \end{array}$$

Observe that $\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ⩽{\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\Rightarrow lg\left(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor \right)⩽lg({\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}})=lg{\mathit{n}}_{\mathbf{1}}-lg{\mathbf{2}}^{\mathit{i}}=lg{\mathit{n}}_{\mathbf{1}}-\mathit{i}.$ Therefore,

$$\begin{array}{cc}\hfill \mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}})⩽& [(\mathbf{2}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathbf{1})+(\mathbf{2}\lfloor lg({\mathit{n}}_{\mathbf{2}}-\mathbf{1})\rfloor +\mathbf{1})+\cdots +(\mathbf{2}\lfloor lg({\mathit{n}}_{\mathbf{2}}-(\mathit{i}-\mathbf{1}))\rfloor +\mathbf{1})]+\hfill \\ \hfill & [(\mathbf{2}lg({\mathit{n}}_{\mathbf{1}}/\mathbf{2})+\mathbf{1})+(\mathbf{2}lg({\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathbf{2}})+\mathbf{1})+\cdots +\hfill \\ \hfill & (\mathbf{2}lg({\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}})+\mathbf{1})]+\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathit{i})\hfill \\ \hfill =& \left[\mathbf{2}\sum _{\mathit{k}=\mathbf{0}}^{\mathit{i}-\mathbf{1}}\lfloor lg({\mathit{n}}_{\mathbf{2}}-\mathit{k})\rfloor +\mathit{i}\right]+\left[\mathbf{2}\sum _{\mathit{k}=\mathbf{0}}^{\mathit{i}}(lg{\mathit{n}}_{\mathbf{1}}-lg{\mathbf{2}}^{\mathit{k}})+\mathit{i}\right]+\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathit{i}).\hfill \\ \hfill ⩽& [\mathbf{2}\mathit{i}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathit{i}]+\left[\mathbf{2}\sum _{\mathit{k}=\mathbf{0}}^{\mathit{i}}(lg{\mathit{n}}_{\mathbf{1}}-\mathit{k}))+\mathit{i}\right]+\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathit{i})\hfill \\ \hfill ⩽& [\mathbf{2}\mathit{i}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathit{i}]+[\mathbf{2}(\mathit{i}+\mathbf{1})lg{\mathit{n}}_{\mathbf{1}}-(\mathbf{1}+\cdots +\mathbf{i})+\mathbf{i}]+\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathit{i})\hfill \\ \hfill =& [\mathbf{2}\mathit{i}\lfloor lg{\mathit{n}}_{\mathbf{2}}\rfloor +\mathit{i}]+[\mathbf{2}(\mathit{i}+\mathbf{1})lg{\mathit{n}}_{\mathbf{1}}-{\mathit{i}}^{\mathbf{2}}]+\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathit{i})\hfill \\ \hfill ⩽& [\mathbf{2}\mathit{i}lg{\mathit{n}}_{\mathbf{2}}+\mathit{i}]+[\mathbf{2}(\mathit{i}+\mathbf{1})lg{\mathit{n}}_{\mathbf{1}}-{\mathit{i}}^{\mathbf{2}}]+\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathit{i})\hfill \end{array}$$

There are two cases to be considered:

• $\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor =\mathbf{1}$ and ${\mathit{n}}_{\mathbf{2}}-\mathit{i}>\mathbf{1}$, then $\mathit{i}⩽lg{\mathit{n}}_{\mathbf{1}}$ and $\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathit{i})⩽\mathbf{\varphi }(\mathbf{1},{\mathit{n}}_{\mathbf{2}}-lg{\mathit{n}}_{\mathbf{1}})⩽\mathbf{2}\lfloor lg({\mathit{n}}_{\mathbf{2}}-lg{\mathit{n}}_{\mathbf{1}})\rfloor +\mathbf{1}⩽\mathbf{2}lg({\mathit{n}}_{\mathbf{2}}-lg{\mathit{n}}_{\mathbf{1}})+\mathbf{1}$. Then,

  $$\begin{array}{cc}\hfill \mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}})& ⩽[\mathbf{2}lg{\mathit{n}}_{\mathbf{1}}lg{\mathit{n}}_{\mathbf{2}}+lg{\mathit{n}}_{\mathbf{1}}]+[\mathbf{2}(lg{\mathit{n}}_{\mathbf{1}}+\mathbf{1})lg{\mathit{n}}_{\mathbf{1}}-{(lg{\mathit{n}}_{\mathbf{1}})}^{\mathbf{2}}]+\hfill \\ \hfill & [\mathbf{2}lg({\mathit{n}}_{\mathbf{2}}-lg{\mathit{n}}_{\mathbf{1}})+\mathbf{1}]\hfill \\ \hfill & =\mathbf{2}lg({\mathit{n}}_{\mathbf{2}}-lg{\mathit{n}}_{\mathbf{1}})+lg{\mathit{n}}_{\mathbf{1}}(\mathbf{2}lg{\mathit{n}}_{\mathbf{2}}+\mathbf{3})+{(lg{\mathit{n}}_{\mathbf{1}})}^{\mathbf{2}}.\hfill \end{array}$$
• $\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor >\mathbf{1}$ and ${\mathit{n}}_{\mathbf{2}}-\mathit{i}=\mathbf{1}$, then $\mathit{i}={\mathit{n}}_{\mathbf{2}}-\mathbf{1}$ and $\mathbf{\varphi }(\lfloor {\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}^{\mathit{i}}\rfloor ,{\mathit{n}}_{\mathbf{2}}-\mathit{i})⩽\mathbf{\varphi }({\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}_{\mathbf{2}}^{\mathit{n}},\mathbf{1})⩽\mathbf{2}\lfloor lg({\mathit{n}}_{\mathbf{1}}/{\mathbf{2}}_{\mathbf{2}}^{\mathit{n}})\rfloor +\mathbf{1}=\mathbf{2}\lfloor lg{\mathit{n}}_{\mathbf{1}}-{\mathit{n}}_{\mathbf{2}}\rfloor +\mathbf{1}⩽\mathbf{2}(lg{\mathit{n}}_{\mathbf{1}}-{\mathit{n}}_{\mathbf{2}})+\mathbf{1}$. Then,

  $$\begin{array}{cc}\hfill \mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}})& ⩽[\mathbf{2}({\mathit{n}}_{\mathbf{2}}-\mathbf{1})lg{\mathit{n}}_{\mathbf{2}}-({\mathit{n}}_{\mathbf{2}}-\mathbf{1})]+[\mathbf{2}(({\mathit{n}}_{\mathbf{2}}-\mathbf{1})+\mathbf{1})lg{\mathit{n}}_{\mathbf{1}}-{({\mathit{n}}_{\mathbf{2}}-\mathbf{1})}^{\mathbf{2}}]+\hfill \\ \hfill & \mathbf{2}lg{\mathit{n}}_{\mathbf{1}}-\mathbf{2}{\mathit{n}}_{\mathbf{2}}+\mathbf{1}\hfill \\ \hfill & =\mathbf{2}{\mathit{n}}_{\mathbf{2}}lg\left({\mathit{n}}_{\mathbf{1}}{\mathit{n}}_{\mathbf{2}}\right)+\mathbf{2}lg{\mathit{n}}_{\mathbf{1}}-lg{\mathit{n}}_{\mathbf{2}}-({\mathit{n}}_{\mathbf{2}}^{\mathbf{2}}-{\mathit{n}}_{\mathbf{2}}+\mathbf{1}).\hfill \end{array}$$

7.3. Bird’s Algorithm Revised

We now establish a revised exact count of the number of comparisons required by Bird’s algorithm [7] in the worst case. Suppose that the algorithm is applied to a two-dimensional ${\mathit{n}}_{\mathbf{1}}\times {\mathit{n}}_{\mathbf{2}}$ array with ${\mathit{n}}_{\mathbf{1}}<{\mathit{n}}_{\mathbf{2}}$. Suppose further, that when a binary search subroutine is called as a part of the algorithm it has worst case performance given in Equation (39). Then, following the reasoning used to derive Equation (17), it can be established that the worst case performance for the revised Bird’s algorithm is

$$\mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}})=\mathbf{4}{\mathit{n}}_{\mathbf{1}}lg\left(\frac{{\mathit{n}}_{\mathbf{2}}}{{\mathit{n}}_{\mathbf{1}}}\right)+\mathbf{6}{\mathit{n}}_{\mathbf{1}}-\mathbf{2}lg\left(\mathbf{4}{\mathit{n}}_{\mathbf{2}}\right).$$

(43)

Note that the count in (43) is significantly higher than that in (17). Recall that from (13), the worst case performance of the adaption of saddleback search for the array under study has a worst case performance of $({\mathit{n}}_{\mathbf{1}}+{\mathit{n}}_{\mathbf{2}}-\mathbf{1})$. However, if it is still assumed that two comparisons are necessary at each iteration of saddleback search, then its worst case performance is

$$\mathbf{\varphi }({\mathit{n}}_{\mathbf{1}},{\mathit{n}}_{\mathbf{2}})=\mathbf{2}({\mathit{n}}_{\mathbf{1}}+{\mathit{n}}_{\mathbf{2}})+\mathbf{1}.$$

(44)

A comparison of Equations (43) and (44) imply that if ${\mathit{n}}_{\mathbf{1}}⩽{\mathit{n}}_{\mathbf{2}}<\mathbf{8}{\mathit{n}}_{\mathbf{1}}$, Bird’s algorithm has an inferior worst case performance than that of adapted saddleback search. Conversely, if ${\mathit{n}}_{\mathbf{2}}⩾\mathbf{8}{\mathit{n}}_{\mathbf{1}}$, the algorithm has a better worst case performance than revised saddleback search.

7.4. The L&S Algorithm Revised

We now establish a revised exact count of the number of comparisons required by the L&S algorithm in the worst case. Suppose that the algorithm is applied to an $\mathit{n}$-cube. Suppose further, that when a binary search subroutine is called as a part of the algorithm it has the worst case performance given in Equation (39). Then, following the reasoning used to derive Equation (31), it can be established that the worst case performance for the revised L&S algorithm is

$$\mathbf{\tau }(\mathit{n},\mathbf{3})⩽\mathbf{3}{\mathit{n}}^{\mathbf{2}}/\mathbf{2}+\mathbf{6}\mathit{n}lg(\mathit{n}+\mathbf{1})+\mathbf{3}\mathit{n}+\mathbf{12}lg(\mathit{n}+\mathbf{1})+\mathbf{6}.$$

(45)

Note that the count in (45) is significantly higher than that in (31).

8. Searching for All Occurrences of the Key

We now briefly discuss the extended problem of searching for all occurrences of the key. To be meaningful, $\mathit{A}$ must be redefined as a strictly monotone array, i.e., its entries either strictly decrease or strictly increase when moving away from the origin along any path parallel to an axis.

When $\mathit{d}=\mathbf{1}$, binary search is the basis for efficiently solving some variants of the search problem, such as determining the index of: ($\mathit{i}$) the first occurrence of the key, ($\mathit{ii}$) the last occurrence of the key, or ($\mathit{iii}$) the least element greater than the key, or ($\mathit{iv}$) the greatest element less than the key. Some minor changes to the basic logic of the Binary Search algorithm are enough to solve variants ($\mathit{i}$)–($\mathit{iv}$). A simple combination of the algorithms that solve variants ($\mathit{i}$) and ($\mathit{ii}$) or of those that solve variants ($\mathit{iii}$) and ($\mathit{iv}$) can be used to determine all occurrences of the key.

Regarding the case $\mathit{d}=\mathbf{2}$, although it was included as an “existence” method, Bird’s algorithm [7] was actually designed to search for all occurrences of the key.

For the case $\mathit{d}⩾\mathbf{3}$, the possibility searching for all occurrences of the key is not discussed in any of the articles cited in the present work. However, certainly, the aforementioned algorithms designed to search for a single instance of the key when $\mathit{d}⩾\mathbf{3}$ can be extended to search for all occurrences of the key, probably with an increase in complexity.

9. Conclusions

The problem of sequentially searching a real $\mathit{d}$-dimensional ($\mathit{d}⩾\mathbf{1}$) array for a given key has been extensively investigated. The formal definition of the problem has been revised and algorithms identified in the specialised literature for it and some of its special cases, including those where the array has sizes not necessarily equal, have been described in detail. Many aspects of algorithm performance complexity have also been discussed. The known $\mathit{d}$-dimensional (balanced and unbalanced) array search algorithms with the best performing complexities in the worst case are shown in

Table 3. Search algorithms and their worst case performance bounds.

d	Structure	Method	Worst-Case Complexity
1	—	Binary Search	$\mathcal{O}(lg(\mathit{n}\left)\right)$
2	Balanced	Saddleback Search	$\mathcal{O}\left(\mathit{n}\right)$
	Unbalanced	Bird/Shen algorithms	$\mathcal{O}({\mathit{n}}_{\mathbf{1}}lg({\mathit{n}}_{\mathbf{2}}/{\mathit{n}}_{\mathbf{1}})),$${\mathit{n}}_{\mathbf{1}}⩽{\mathit{n}}_{\mathbf{2}}$
3	Balanced	L&S algorithm	$\mathcal{O}\left({\mathit{n}}^{\mathbf{2}}\right)$
4	Balanced	Cheng-4 algorithm	$\mathcal{O}\left({\mathit{n}}^{\mathbf{3}}\right)$

for $\mathbf{1}⩽\mathit{d}⩽\mathbf{4}$. It can be seen from the table that each algorithm has order strictly less than a product of the sizes of the array, except for the $\mathit{d}=\mathbf{2}$ balanced case.

A present challenge is to solve recurrences such as the one in (32). Open problems include those of finding efficient algorithms for $\mathit{d}$-dimensional unbalanced arrays with $\mathit{d}⩾\mathbf{3}$.