Searching in an array in less than O(n) time

Question

I have an array where each element is either one less or one greater than the preceding element \$\{x_i = x_{i-1} \pm 1\}\$. I wish to find an element in it in less than \$O(n)\$ time. I've implemented it like this:

public int searchArray(int[] arr, int i, int elem) {

    if (i > arr.length - 1 || i < 0) {
        return -1;
    }

    if (arr[i] == elem) {
            return i;

    } else {
            int diff = Math.abs(elem - arr[i]);
            int index = searchArray(arr, i + diff, elem);
            if (index == -1) {
                index = searchArray(arr, i - diff, elem);
                if (index == -1) {
                    return -1;
                }
            }
            return index;
    }
}

And calling it like:

int[] arr = {2, 1, 2, 3, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4};
int index = searchArray(arr, 0, 3);

It is working fine, but can it be improved? Specifically, is there a way to do it iteratively? And is the current algorithm less than \$O(n)\$. I guess it is, but I'm not sure.

Answer 1

While other answers make good points, I have to wonder why you are using recursion. This is such a simple problem to solve with a for loop.

I assume that you are not supposed to start from any index other than index 0, so consider the following routine:

public int searchArray(int[] arr, int elem) {

    for (int i = 0; i < arr.length; ) {
        if (arr[i] == elem) {
            return i;
        }
        i += Math.abs(elem - arr[i]);
    }
    return -1;
}

(If you need to start the search part-way through the array then you can add the offset input parameter again and start i from that).

The bottom line is that recursion is overkill, this system is \$O(n)\$, but the cost of each cycle is less than the same thing using recursion.

I am not aware of any way to solve the given problem with a system of better than \$O(n)\$ complexity.

---

Discussion on complexity - why this is \$O(n)\$

This answer has generated a lot of discussion about complexity, that this method only ever scans, at most, half the members of the input array, and thus it should be complexity \$O \left( \frac{n}{2} \right )\$ instead of \$O(n)\$. The argument given is something like:

Consider the worst-case data 1,2,1,2,1,2,1,2,1,2,1,2 and the search term 3. For this situation the method will start at data[0], and then skip to data[2], then data[4], and so on. It will never inspect data[1], and other odd-indexed data points. If the search term is even more 'different' than the actual data (e.g. 100) then the method will do only one comparison at data[0] and will then return 'not found' -1.

This is an interesting observation, that the method only ever needs to scan half the data at most. This is especially interesting considering a 'naive' method which just scans the data one-member-at-a-time and returns when it finds the value. That 'naive' method most certainly has \$ O\left(n\right) \$ 'performance' and complexity, and the 'skip-method' will be more than twice as fast.

The important thing to note though, is how the algorithms scale relative to the amount of data, not relative to each other!

So, consider a hypothetical set of worst-case data 1,2,1,2,1,2,.... and the search-term 3. This hypothetical happens to be searched in 4 milliseconds by the skip-method, and in 8 milliseconds by the naive-method. Now we double the amount of data, what happens? The processing time for both methods will double!

In both cases, the performance of the algorithms will double for each doubling of the data volume. This is what makes both algorithms \$ O(n) \$ complexity. From Wikipedia:

In computer science, big O notation is used to classify algorithms by how they respond (e.g., in their processing time or working space requirements) to changes in input size.

Reversing the argument, by suggesting the skip-method has \$O \left( \frac{n}{2} \right) \$ complexity, I would then expect that, if I double the data, the execution time would only increase by a half, or 50%. This is 'obviously' not true for the skip-method (nor the naive-method).

Both methods have \$O(n)\$ complexity because they both scale the same way with increasing volumes of data.

But, just because they scale the same way, does not mean that one method is not better than the other... obviously.

Answer 2

The problem is in \$O(n)\$. Consider the case that 200_success describes.

You have a sequence of alternating 1 and 2's where a single 1 is replaced by a 3.

When you are asked to search for a 3 you know, after inspecting the first element, that it will have an even index. But if every odd index holds a 2 then any even index can hold a 3, so you can not guarantee that the 3 is not in the last index you search. This means that you will have to look in \$O(\dfrac{n}{2})\$ places. \$O(\dfrac{n}{2})\$ = \$O(n)\$, so the problem is \$O(n)\$.

No correct algorithm can have better worst time performance than this.

A more interesting question is what happens if you know that no number occurs more than some fixed upper bound.

Answer 3

You never need to look backwards if you start at 0.

Proof by induction over algorithm steps j:

For j = 0, i(j) = 0, you cannot go backwards.

For j > 1, there are two cases: First one, we found our number. Second one, there is a difference diff(j) = abs(elem - array[i(j)]). Then no number in array[i(j),i(j)+diff) can contain elem. By induction hypothesis, no element in array[i(j-1),i(j)=i(j-1)+diff(j-1)) contains that number either. So the next possible index for i is i(j)+diff(j) (= i(j+1))

But that algorithm really is in O(n) as Taemyr already answered.

Answer 4

Here's some generic advice first:

• Avoid single-letter parameter names. For small loops i is fine, but it shouldn't leak into method signatures--especially when index is only four more letters.

• Be consistent with if-else. You have two if blocks that both return from the method, either use else with both or neither. Otherwise it appears at a quick glance that one doesn't exit.

  if (x)
      return foo;
  else if (y)
      return bar;
  else
      baz
  

  or

  if (x)
      return foo;
  if (y)
      return bar;
  baz
  

• if (index == -1) return -1; is redundant since it's immediately followed by return index;.

• Math.abs is unnecessary since you first add and then subtract diff. The order doesn't matter here.

• I would reverse the i and elem parameters and add an overloaded form that omits i and simply calls the other with i = 0. This provides a nicer API for callers. The three-parameter version could also be private to the class containing both if only the latter form is needed externally.

As to your question about the time complexity, my gut says that it is probably possible for the worst case to cause an infinite loop, but I haven't delved too deep in the actual algorithm yet.

To rewrite this iteratively you'll need to use a stack to allow backtracking since you sometimes need to branch both directions. Here's a quick stab at it in psuedocode:

search(int[] arr, int find)
    return search(arr, find, 0)

search(int[] arr, int find, int index)
    stack = [-1]
    while (index != -1)
        if (0 <= index && index < arr.length)
            elem = arr[index]
            if (elem == find)
                return index
            else
                diff = find - elem
                stack.push(index + diff)
                stack.push(index - diff)
        index = stack.pop();
    return -1

Answer 5

This can be done in O(1) time, if it is ok to use O(n) time to build a lookup-table just once. If the array stays the same, and you're going to search multiple times, this might be a good approach. The following pseudocode assumes you're going to search the whole array (from index 0), and returns the first index where the element is found. It can easily be modified to search from an index > 0, and also tell you all the indices where the element occur.

Say your input array is called arr, the length of arr is n, and arr[0] is k. We know that the values in arr are in the range [k-n+1,k+n-1], in total 2n-1 different values. For each possible integer in the range, we make an entry for it in our lookup table:

// Initialization
for i = 0 to 2n-2 
    lookup[i] = -1

k = arr[0]

// Build lookup-table
for i = 0 to n-1
    index = arr[i]-k+n-1
    if lookup[index] == -1
        lookup[index] = i // We only store the position in arr of the first occurrence


// Search for, say, s (assuming s is in the valid range, no check for it here)
lookup[s-k+n-1] // A result >= 0 is a hit, giving the (first) position of s in arr

Answer 6

public static int search(int[] array, int start, int end, int target)
{

    if(array[start] == target)return start;
    if(array[end] == target)return end;
    if(Math.abs(array[start]-target) + Math.abs(array[end]-target) >= end-start+1)
        return -1;


    int middle = (start+end) / 2;

    int val = search(array, start, middle, target);
    if(val != -1)return val;

    val = search(array, middle+1, end, target);
    if(val != -1)return val;

    return -1;
}

This is what I came up with. It actually splits the list down the middle. After each split it checks if it's possible for the target to be in this array. Math.abs(array[start]-target) + Math.abs(array[end]-target) >= end-start+1 covers that(it uses the fact that you have to get from the first number to target, then back down to the last number in the array). If it is possible, we continue splitting on that until the target is the beginning or end of a range.

For an example of how this cuts, consider an array starting and ending in 1, and it's only length 5. You are asked to find 4 in it. You know this is impossible, since you need to spend 3 slots getting to 4, and then 3 back down to one. This means the length needs to be at least 7. So we can return -1 immediately.

This does actually even help a little bit in the case of 12121212121212.....321212 because you often get sublists of 121 which can't have a 3.

That being said. It still looks O(n) on worst case to me. Though I wouldn't be surprised if this has a sub-linear average case.

Answer 7

The function should be

public static int searchArray(int[] array, int value) {
    // Call private static int searchArray(int[] array, int index, int value)
    return searchArray(array, 0, value);
}

… because if the caller can pick any starting index, the result could be wrong. (Consider searchArray(arr, 12, 6) in your example.) The functions should be static since they rely on no instance variables.

I believe that the worst case would be at least O(n), as in the following example:

int[] arr = {1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 1, 2, 3};
int index = searchArray(arr, 0, 3);

Answer 8

There are a lot of good answers here, but I felt like taking a stab at the question.

If your task is to search the array with \$O(n)\$ or less complexity, I most smugly propose:

int search(int[] data, int value) {
    for (int i = 0 ; i < data.length ; i++) {
        if (data[i] == value) {
            return i;
        }
    }
    return -1;
}

So I doubt that's the case; either the original asker incorrectly used big \$O\$ to refer to running time, or you're really over-complicating the search.

Assuming they meant running time \$R < k*N\$ my solution below differs from yours in two important respects:

It seems you understand that you can save time by skipping ahead, exploiting the fact that for two values \$x\$ and \$y\$ at indices \$i\$ and \$j\$ respectively where \$i < j\$, \$y \le x + j - i\$ and \$y \ge x + i - j\$. However, your algorithm goes ahead and searches backward after it skips ahead; this is not necessary. You can skip ahead because the search value can't be in the range you skipped.

Recursion is not recommended because it expands the storage requirements for the algorithm by occupying stack, makes the complexity of the algorithm more difficult to evaluate, and usually increases \$k\$. It is perfectly possible to search with a loop that is easily shown to be \$O(n)\$ time and \$O(k)\$ space complexity.

int searchWeirdlyOrganizedArray(int[] data, int forValue) {
    int i = 0;
    while (i < data.length) {
        if (data[i] == forValue) {
            return i;
        } else {
            i += abs(forValue - data[i]);
        }
    }
    return -1;
}

Final note: I was wrong in my comment that searching \$\lbrace1, 2, 1, 2, \dots\rbrace\$ for 3 would require \$N\$ comparisons. It requires \$\frac{N}{2}\$ comparisons because all the 2s are skipped over. If the 2s and 1s are reversed (\$\lbrace2, 1, 2, 1, \dots\rbrace\$) it takes \$1 + \frac{N - 1}{2}\$ comparisons, as the initial comparison only advances the search by 1, but thereafter every 2 is skipped. However, I was right that it is still \$O(n)\$ complexity.

Answer 9

I don't think you will find a better worst-case than \$O(n)\$. But if you want to do a lot of queries on one array (i.e. check multiple numbers in single array), you can use counting sort.

There is one improvement that can be done here that works in \$O(n)\$ preprocessing and \$O(1)\$ time for each query. That is, you can do \$t\$ queries in \$O(t + n)\$ time, not in \$O(nt)\$, as you would need to do with your current method.

One obvious way is to sort your array in \$O(nlogn)\$ and do binary searches in \$O(logn)\$. For \$t\$ queries, time would be \$O(tlogn + nlogn)\$. But that can still be improved.

You can sort your numbers in \$O(n)\$ time using counting sort, but there is one trade-off this way. That is, if the biggest number in the array is \$k\$, then you need an array of size \$k\$ in your RAM, which would cause problems in rare cases.

This code only works for non-negative integers. With a little change, the algorithm would work for negative integers as well.

Answer 10

Here is a different solution:

public static void radixSort(int[] data) {
    boolean flag = true;
    int divisor = 1;
    Queue [ ] buckets = new Queue[10];
    for (int i = 0; i < 10; i++)
            buckets[i] = new LinkedList();

    while (flag) {
            flag = false;
            // first copy the values into buckets
            for (int i = 0; i < data.length; i++) {
                    int hashIndex = (data[i] / divisor) % 10;
                    if (hashIndex > 0) flag = true;
                    buckets[hashIndex].add(data[i]);
            }
                    // then copy the values back into vector
            divisor *= 10;
            int i = 0;
            for (int j = 0; j < 10; j++) {
                    while (! buckets[j].isEmpty()) {
                            Integer ival = (Integer) buckets[j].element();
                            buckets[j].remove();
                            data[i++] = ival.intValue();
                    }
            }
    }
}

public static int searchArray(int[] arr,int offset,int elm) {
    radixSort(arr);
    return Arrays.binarySearch(arr, elm);
}

The first part, radixSort, is \$O(kn)\$ and the second part, binarySearch, is \$O(log(n))\$. Alternatively to writing radixSort, you could have used the standard Java Arrays.sort which has an order of \$O(n log(n))\$ because it's an implementation of quick sort.

This was my old solution which as was pointed out is still \$O(n)\$:

The solution is fairly simple. You can optimize this down to \$O(\frac{n}{2})\$, simply because when you look at the value of an item, you know what the value of the item before and after that item is.

The simple function would be:

public int searchArray(int[] arr,int offset,int elm) {          
     if(arr != null && arr.length > (offset+1)) {
            for(int i = (offset+1); i < arr.length; i+=2) {                
                int absVal = Math.abs(elm - arr[i]);
                if(absVal == 1) {
                    int behind = i - 1;
                    int infront = i + 1;
                    if(arr[behind] == elm) {
                        return behind;
                    } else if(arr[infront] == elm) {
                        return infront;
                    }
                } else if(absVal == 0) {
                    //we are the value
                    return i;
                }
            }
        } else if(arr != null && arr.length > offset && arr[offset] == elm) {
            return offset;
        }                    
        return -1;              
    }

Here is a complete sample program that will also run a regression test on the entire code example for every element in the array to prove that it works. I also included a counter to show the number of cycles that were actually performed. Since we increment the array counter by 2 in any case, the maximum order of the algorithm will always be lower that \$O(n)\$.

Complete code sample:

package cstura;

import javax.xml.ws.Holder;

/**
 *
 * @author cstura
 */
public class Test {

    public static void main(String[] args) throws Throwable {
        int[] arr = {2, 1, 2, 3, 4, 3, 2, 3, 4, 5, 6, 5, 4, 3, 4};        
        for(int i = 0; i < arr.length; ++i) {
            Holder<Integer> numItrs = new Holder(0);
            int idx = searchArray(arr,0,arr[i],numItrs);
            System.out.println(String.format("first position of %d in the array is: %d total itrs were: %d",arr[i],idx,numItrs.value));
        }
    }

    public static int searchArray(int[] arr,int offset,int elm,Holder<Integer> numItrs) {
        int itrs = 0;
        try {            
            if(arr != null && arr.length > (offset+1)) {
                for(int i = (offset+1); i < arr.length; i+=2) {                
                    itrs++;
                    int absVal = Math.abs(elm - arr[i]);
                    if(absVal == 1) {
                        //the value if infront or behind us (maybe)
                        int behind = i - 1;
                        int infront = i + 1;
                        if(arr[behind] == elm) {
                            return behind;
                        } else if(arr[infront] == elm) { //if it's not behind then it must be infront.
                            return infront;
                        }
                    } else if(absVal == 0) {
                        //we are the value
                        return i;
                    }
                }
            } else if(arr != null && arr.length > offset && arr[offset] == elm) {
                return offset;
            }

            return -1;  
        }finally {
            numItrs.value = itrs;
        }
    }        
}

Answer 11

I'm sure there are algorithms that, on average, are better than \$O(n)\$ on average.

For instance, if a search algorithm searches array source, length length, indexing through with variable index searching for target, then if source[index] != target, then the next value for index could be index + abs(source[index]-target), which might skip many elements, or even run off the end of the array and terminate.

That is, you only need to check a few elements of the array since their values are constrained.

A better mathematician than me will be able to tell you what the upper bound is, but my guess would be \$O(1)\$.

Answer 12

Is there a restriction that says the array has to (or can't be) in a specific order? If you keep a sorted array you could perform a binary search which would run in O(log(n)). There are both recursive and iterative implementation. Of course the drawback is that the array has to be sorted but the pro is that you can search through millions of records in less than 10 iterations/recursions.

From Wikipedia's article on the binary search algorithm:

int binary_search(int A[], int key, int imin, int imax)
{
  // test if array is empty
  if (imax < imin)
    // set is empty, so return value showing not found
    return KEY_NOT_FOUND;
  else
    {
      // calculate midpoint to cut set in half
      int imid = midpoint(imin, imax);

      // three-way comparison
      if (A[imid] > key)
        // key is in lower subset
        return binary_search(A, key, imin, imid-1);
      else if (A[imid] < key)
        // key is in upper subset
        return binary_search(A, key, imid+1, imax);
      else
        // key has been found
        return imid;
    }
}