Find pair of numbers in 2 dimensional array in C#

what is the fast way to find pair of numbers in 2 dimention array

i have this array

 int[,] numbers = new int[,] { { 5, 2 }, { 5, 1 }, { 5, 0 } , ........... };

i have to integers like x,y

i want to return the index of this pair apper in the array

if the pair dont 开发者_运维知识库exist retun false

thanks

If the array is not ordered, the best you can do is a linear search - either row by row, column by column, or even by diagonal.

If either of the dimensions of the array are ordered, then you could use binary search.

If the data is ordered and also conforms to some kind of distribution, you could use a distribution correlation lookup, which could be slightly more efficient than binary search.

If the array is ordered you can use a binary search. Otherwise you will have to do a linear search.

Do the sorting of 2D array and then use Binary search.

"Fastest" is vague; fastest to write, or fastest to execute?

The fastest you could get this on an unordered list would be linear, and the actual best and worst cases would depend on the input data. The fastest overall on an unordered list would probably be:

var i = 0;
foreach(var subarray in numbers)
{
   if(subarray[0] == x && subarray[1] == y || subarray[0] == y && subarray[1] == x)
     return i;
   i++;
}

Best case is that the first element has the elements in order; 1 element, 2 equality comparisons. Worst case is it's not there; n elements, n*4 equality comparisons.

You can "fail fast" in situations where it is unlikely that a match will be found, by checking to see if the subarray has at least one element with at least one of the coordinates. If not, don't bother checking for an exact match. That makes the worst case that the element is the last one, out of order (n*2 elements, n*6 comparisons), but the best case is that it isn't there (n elements, n*2 comparisons, which if this case is likely is better than the previous).

Lastly, the "fail fast" algorithm allows for using Linq to narrow the number of elements on which you make the full set of conditional checks; you first look for elements that have at least one of the coordinates (requiring a max of two checks), then check only those for elements that match exactly (a max of four checks). Then, you scan the array for the first element you found, which is a relatively fast referential check.

var result = numbers.Where(a=>a[0] == x || a[0] == y)
   .Where(a=>a[0] == x && a[1] == y || a[0] == y && a[1] == x)
   .FirstOrDefault();

if(result != null) return Array.IndexOf(numbers, result);

Best case, it's not there (n elements, n*2 comparisons). Only slightly worse is the probably-likely case that only one element has either of the coordinates (n+1 elements, n*2+(2 or 4) comparisons). Worst case, the match is the last element, out of order, AND every element in the list has a first coordinate that is x or y (n*3 elements, n*7 comparisons, but this is EXTREMELY unlikely in most real data). The average case will depend on the number of elements that have at least one of the coordinates as its first value.