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