Is there a faster alternative to Array.Exists for huge sorted int arrays?

I am having two sorted int Arrays (both one-dimensional, Array1 could have up to several million entries, Array2 will probably be a lot smaller, I am thinking six figures, no duplicates) where I have to perform a matching operation. I am wondering if simply using Array.Exists would be the fastest way to do it or if there is a faster method specifically for finding exact matches of numbers.

Jon Skeet
people
quotationmark

If it's sorted, you can use Array.BinarySearch which will be O(log n) instead of O(n):

int index = Array.BinarySearch(sortedArray, targetValue);
if (index >= 0)
{
    // Found!
}

(BinarySearch returns a negative number if the value wasn't found; that's the bitwise complement of the index at which you would insert the value to maintain ordering.)

Alternatively, if your values are distinct, try creating a HashSet<int> instead of the array - that will take more memory, but may provide an even faster lookup. It's amortized O(1) instead of O(log N), but the constant factor may well make the binary search quicker anyway. You should definitely test this rather than assuming one will be faster than the other.

Note that even for linear searches, if you're looking for an equality match then Contains is simpler than Exists, as you don't need to provide a delegate (just a value).

people

See more on this question at Stackoverflow