Search an array
I have an array int x[] and a number. I like to do search on the array such that x[i] + x[i+1] = number.
What is the most effici开发者_如何学JAVAent and fastest way in Java?
Here is a pseudo code, this should work. Only n memory reads.
buff1 = x[0]
buff2 = 0
for i = 1 to n - 1
buff2 = x[i]
if (buff1 + buff2) == number
then
MATCH
endif
buff1 = buff2
endfor
If the array is unsorted and your only doing a few searches use phoxis' method. It's expected to run in O(n*k), where n is the size of x, and k is the number of searches you wan't to make.
If the array is sorted, we know that x[i]<=number/2 and x[i+1]>=number/2. Use binary search to find the (last) predecessor to number/2+1, and check if the match.
int i = binaryPredecessor(x , number/2 + 1);
if(x[i] + x[i+1] == number){
return i;
}
else if(x[i-1] + x[i] == number){
//The case where x[i] == number/2, and we found the last of two occurrences
return i-1;
} else {
//No match exists
return -1;
}
The runtime is O(log(n)*k).
If you do a lot of searches, it might be worth while to sort the array, and use the above method. The array can be sorted in O(n*log(n)) [see mergersort]. So if you want to do more log(n) searches, it's worth to sort the array. (If k is close to log(n), do some testing, to see whats best :) )
精彩评论