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

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.

-
@DavidHarkness To my surprise, it didn't go into infinite recursion with that. In fact, the iterative approach broke. OutOfMemory. – user3011937 Dec 3 '13 at 7:06
That's because the stack outgrew the available memory. If memory had been infinite, the method would never terminate. I don't see how the recursive method could work, though. – David Harkness Dec 3 '13 at 7:07
When you say "less than O(n)", do you mean that a worst case O(n) is unacceptable, or that O(n - 1) is fine despite being equivalent to O(n) in complexity because it's less than O(n)? I would assume the former, but it doesn't seem possible to search {1, 2, 1, 2, ...} for 3 without comparing all but one element. I can see reducing the average running time by splitting up the array into ascending and descending sequences, but that won't get around the worst case for a non-match in an array of alternating elements. – sqykly Dec 3 '13 at 8:29
I'm wondering whether the phrase "less than O(n)" even has a well-defined meaning. O(n) already implies an upper bound on the resources an algorithm takes. Remember that O(n/2) is not less that O(n). If the question asked for an O(log(n)) algorithm, that would be a meaningful question. – LarsH Dec 3 '13 at 14:56
It seems there is some contention about O(n) vs O(n/2). Back when computers were slow and assembly programmers were cool, the phrase "never ignore k" was heard often. That comes to mind as I comment: complexity != running time. Run time is k times O for relevantly large n. "O(n/2)" is at worst gibberish, at best shorthand for "O(n) with k = 1/2 of some reference algorithm". O(n/2) complexity is not better than O(n). k(n/2) run-time is better than k(n). – sqykly Dec 4 '13 at 10:24

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.

-
@user3011937 The solution in my example will always find the first matching value from the start position (which I have set to 0 but it can be easily changed by adding a parameter). Because of the rules for the data (index[n] = index[n - 1] +/- 1, you can always move forward and never have to move backward. I think you should do some debugging of the various solutions, or work them out on paper.... really, this works. – rolfl Dec 3 '13 at 12:23
"A good programmer knows how to use recursion. A great programmer knows when not to." --Anonymous – Plutor Dec 3 '13 at 13:57
This is a fine algorithm, but what makes anyone think that it takes "less than O(n)" time? Sure it doesn't require examining all n elements in the array, but saying it takes less than O(n) time implies that as n grows, the time to complete the algorithm grows more slowly than n. Is there any evidence of that? (Let's say in the average case, let alone the worst case.) – LarsH Dec 3 '13 at 14:58
@xuwicha - indeed, but O(n/2) is still O(n) – rolfl Dec 4 '13 at 3:45
@xuwicha - actually, if you double the amount of data the algorithm will take twice as long, hence O(n) ... – rolfl Dec 4 '13 at 3:59

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.

-
This should have been the accepted answer, as it's the only one so far that deals correctly with the question of finding a "less than O(n)" algorithm. – LarsH Dec 3 '13 at 15:04
@LarsH Well OP also asks how his algorithm can be improved. And from context it's fair to assume that this is the most important part of the question. So I don't feel too bad about which answer was accepted. Esp since this is codereview rather than cstheory. – Taemyr Dec 3 '13 at 15:49

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))

-
Got it. Very nice. Thank you so much for induction :) Let me clear myself. Just going forward will get me the element if there is. And if there are more, I'll automatically get the very first element right? – user3011937 Dec 3 '13 at 12:40
@user3011937 Not only that, but because you're always going in one direction you eliminate the possibility of an infinite loop. – David Harkness Dec 3 '13 at 23:19

• 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

-
Hi David. Thanks for those valuable tips. I've done the modification in my original code as per the suggestion. But the iterative approach is not working. It is always returning -1. – user3011937 Dec 3 '13 at 6:25
Ok, your code will fail if the diff comes out to be -1. That is what happening currenly. If I search for 3, and first element is 2, it breaks. I'm trying to fix it. – user3011937 Dec 3 '13 at 6:27
Fixed it. No need to push anything in the stack before loop. And I changed outer while loop to while (true);, and removed the return statement after it. Thanks you so much. If you have better way to solve this, except while (true), please do share. – user3011937 Dec 3 '13 at 6:29
@user3011937 The initial -1 value in the stack is to indicate when we run out of indexes to check and thus the element was not found. You could do the same thing with stack.isEmpty checks, but I found using the poison pill value simpler. Note that I used indentation instead of braces since it's psuedocode: the two push calls must happen only in the else block with diff. – David Harkness Dec 3 '13 at 6:36
@ChrisWue I did a poor job of explaining myself. Hopefully my edit to the second bullet is clearer. – David Harkness Dec 3 '13 at 6:52

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

-
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.

-
This is a good suggestion... the OP's question did not specify whether the result had to be the 'first' index. Your solution would give O(log(n)) if the question is whether to get any hit.... But, even then, it could, with the right depth-first-approach work well. The best-case for a simple loop is going to be faster, but your worst case would be much better than the simple-loop worst case – rolfl Dec 3 '13 at 17:14
Actually, I have worked through your solution, I think the worst case will be slower than the worst-case for the simple-loop option. for the data 1,2,1,2,1,2,1,2,1,2,1,2,1,2,3,2,1 it would do as many, operations as a simple loop, and carries the recursion overhead. Your solution is very similar in performance to the loop, which also 'skips' blocks where the value is impossible. – rolfl Dec 3 '13 at 17:27
@rolfl This solution does actually find the first index. Since I recurse through the first half first. I only look at the second half when the first half returns not found. However, yes it does still have a bad worst case. I just thought I'd present a slightly different way of looking at the problem :) – Cruncher Dec 3 '13 at 17:37
I have been stewing through this solution of yours, and it has me intrigued. But, in my (almost) final analysis, the iterative solution will always find the first matching solution before the recursive solution, and it will always require fewer comparisons. Despite my initial though that your solution has a log(n) complexity, I am now, surprisingly, convinced it is also plain O(n). This only holds true if the goal is to return the first match. – rolfl Dec 3 '13 at 21:04
@rolfl I'm glad that I've intrigued you xD. It's probably provable actually that O(n) is the optimal worst case. I pretty much assumed that from the beginning. What I'm more interested is average case, which I am terrible at analysing(not to mention how difficult this solution is to analyse). Do you think that can hit log(n) complexity on average? – Cruncher Dec 3 '13 at 21:20

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);

-
do you have any better way? So that worst case is less than O(n)? What if we start from middle? Or some random location? – user3011937 Dec 3 '13 at 7:18
Starting from the middle would cut the time in half, at best. O(n / 4) is still O(n). Same argument goes for starting anywhere else. – 200_success Dec 3 '13 at 7:25

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.

-
Just a bit confused. I am trying to see whether there is anything significantly different (apart from the while-vs-for loop) between your suggested code and the accepted-answer code. Am I missing something? – rolfl Dec 24 '13 at 17:11
@rolfl Code doesn't look different. I don't like the for with a modification to i in the loop body. Discussion and comparison to the OP's code is a little different. Also, I offer a cheeky solution to the problem as originally stated if interpreted literally. I should probably upvote the accepted answer in agreement, though, eh? – sqykly Dec 24 '13 at 23:27

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.

-

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++)

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;
}
// 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) {
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;
}
}
}

-
O(n/2) is not lower than O(n), it is exactly the same as O(n). – svick Dec 4 '13 at 12:50
this statement doesn't make much sense. because n/2 does half as many clock cycles in a worst case scenario as O(n) which means that it is not the same it's faster. the be precise the algorithm is always twice as fast. – cstura Dec 4 '13 at 14:08
Then you most likely don't understand what the big O notation actually means. When comparing algorithms, it's hard to compare “n/2 slow iterations” and “n fast iterations”. So you use the big O notation to say that both are about the same and that the real difference is between, say, O(log n), O(n) and O(n^2). – svick Dec 4 '13 at 14:16
Welcome to Code Review. Answers should contain some critique of the original code. If you present your own code, please justify why it is better. (Shorter? Faster? Easier to understand? …) – 200_success Dec 4 '13 at 17:29

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)$.

-
In the worst case, abs(source[index]-target) is always less than or equal to 2, and so this algorithm only skips half of the elements, making it O(n/2), which is the same thing as O(n). – Tanner Swett Feb 24 '14 at 22:05
@TannerSwett: I'm not convinced that abs(source[index]-target) is always less than or equal to 2. – quamrana Feb 25 '14 at 11:03
I'm not claiming that abs(source[index]-target) is always less than or equal to 2. I'm saying that if abs(source[index]-target) is less than or equal to 2 throughout some array, then no algorithm can successfully search that array faster than O(n). – Tanner Swett Feb 27 '14 at 1:09

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)
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;
}
}

-
Having a pre-ordered array would not help with the OP's problem (in fact it would break it...). The original problem requires the data to be in a predefined (unordered) sequence – rolfl Dec 3 '13 at 16:54
@rolfl With the OP's requirement an ordered list is not impossible, but certainly not assumable. This is just addressing that you said an ordered array would break the OP's problem, when it wouldn't necessarily. – Cruncher Dec 3 '13 at 18:04
@Cruncher - of course, and you are right to point out the inconsistency in my statement, but, forcing an order woud certainly break the OP's requirement. – rolfl Dec 3 '13 at 18:17