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.

Are all the values in the array unique and ordered? And is the array modified between calls? — Tony
– Tony, Commented Mar 7, 2011 at 12:52
I think this question is more relevant to codereview.stackexchange.com — Peter Porfy
– Peter Porfy, Commented Mar 7, 2011 at 12:52

Konrad Rudolph · Accepted Answer · 2011-03-07 13:00:05Z

9

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

edited Mar 7, 2011 at 13:00

answered Mar 7, 2011 at 12:54

Konrad Rudolph

549k142 gold badges967 silver badges1.3k bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

BlueVoodoo Over a year ago

id (806) is not a part of the array. 801 is in the array and 1600 is in the array. I want 801 to be returned when 806 has been given.

Konrad Rudolph Over a year ago

@BlueVoodoo That’s no problem. The code works even then, just subtract 1 from the bitwise complement of result.

Jon Skeet Over a year ago

@BlueVoodoo: Look at the docs for BinarySearch and what it returns if the ID isn't found.

Ondrej Tucny · Accepted Answer · 2011-03-07 12:54:30Z

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.

answered Mar 7, 2011 at 12:54

Ondrej Tucny

28.2k6 gold badges73 silver badges93 bronze badges

3 Comments

BlueVoodoo Over a year ago

id (806) is not a part of the array. 801 is in the array and 1600 is in the array. I want 801 to be returned when 806 has been given since it's between the two.

Ondrej Tucny Over a year ago

@BlueVoodoo Binary search is a trivial algorithm and you can implement it in a way that lets you select either the lower or upper match in case the input is not exactly present in the array. Please note that to use that algorithm the array must be sorted.

BlueVoodoo Over a year ago

Thanks. The array is sorted at all times so that shouldn't be an issue.

Collectives™ on Stack Overflow

C# - Help optimizing a loop

2 Answers 2

3 Comments

3 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

3 Comments

Your Answer

Sign up or log in

Post as a guest

Related