C# - Help optimizing a loop

Question

I have a piece of code that in principal looks like the below. The issue is that I am triggering this code 10's of thousands of times and need it to be more optimized. Any suggestions would be welcome.

//This array is in reality enormous and needs to be triggered loads of times in my code
int[] someArray = { 1, 631, 632, 800, 801, 1600, 1601, 2211, 2212, 2601, 2602 };

//I need to know where in the array a certain value is located
//806 is located between entry 801 and 1600 so I want the array ID of 801 to be returned (4).
id = 806

//Since my arrays are very large, this operation takes far too long 
for (int i = 0; i < someArrayLenght; i++)
{
  if (someArray[i] <= id)
    return i;
}

Edit: Sorry got the condition wrong. It should return the id when 806 is greater than 801. Hope you can make sense ot ouf it.

Answer 1

The array values look sorted. If that’s indeed the case, use binary search:

int result = Array.BinarySearch(someArray, id);
return result < 0 ? (~result - 1) : result;

If the searched value does not appear in the array, Array.BinarySearch will return the bitwise complement of the next greater value’s index. This is why I am testing for negative numbers and using the bitwise complement operator in the code above. The result should then be the same as in your code.

Binary search has logarithmic running time instead of linear. That is, in the worst case only log₂ n many entries have to be searched instead of n (where n is the array’s size).

Answer 2

Providing someArray's content is sorted, use binary search — see also Array.BinarySearch.

Note: In your example the condition in if (someArray[i] <= id) return i; will trigger whenever id >= 1. I doubt that's what you want to do.