# How to get an O(n) for a search algorithm [duplicate]

This question already has an answer here:

Given an two sorted arrays X and Y, both of size n. Determine if there is an element x of X and an element y of Y such that x = 3y. The algorithm needs to run in linear time in the worst case. At the moment, the algorithm runs in O(n^2). I am unsure how to leverage the fact that the algorithm is sorted to have a scenario where the worst case would have O(n). I am aware of the fact that a binary search has O(log n).

public static void main (String [] args)
{
int[] listX = {1,2,3,4};
int[] listY = {1,2,3,8};

for(int x = 0; x<listX.length; x++)
for(int y = 0; y<listY.length; y++)
{
if(listX[X] == (3*listY[y]))
{
System.out.println("TRUE");
break;
}

}
}


## marked as duplicate by Evil, vonbrand, Community♦Sep 24 '15 at 6:44

• Imagine walking one of the arrays, wlog X; you did your commendable best to find y, found none, but the positions of the "closest below and above": how does this help you for the next x? (Next, have a look at Galloping search.) – greybeard Sep 23 '15 at 7:30
• Hello! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. Have you tried looking for a way to use binary search? – D.W. Sep 23 '15 at 16:07
• @D.W. Although there are a couple of Java keywords in there, I think the code is generic enough that it can be understood as pseudocode as-is. – David Richerby Sep 23 '15 at 20:26
• Related question. Also, what is your question? – Raphael Sep 23 '15 at 22:10

If we imagine that every element of Y is multiplied by 3 in-place in a first step, the problem then becomes equivalent to finding whether there is a common element in the resulting list and X. The required algorithm is similar to the algorithm for merging two sorted lists into a single sorted list, which has a well-known solution in linear time.

The pseudo-code for the solution of O(n) is:

for (x=0, y=0; x < listX.length && y < listY.length; ) {
if (listX[X] == (3*listY[y])) {
print TRUE;
break;
}
if (listX[X] < (3*listY[y])) {
x++
} else {
y++
}
}

• Please add some explanation to your answer: a (pseudo)code dump and a claim don't add up to much. – David Richerby Sep 23 '15 at 12:20