Sek said:
Folks,
I have an ArrayList of integers.
I have sorted the list already.
Now, i want to find the index of the first element that is greater than
a given number.
How to accomplish this in C#?
Hi,
As other people have explained BinarySearch is a good way to go. The drawback, in your case, is that
it will find the EXACT value and not the value greater than the one that you want.
However, BinarySearch has a nice feature. If it DOESN'T find what it is looking for it will return a
negative number, which is the bitwise complement of the index of the next element. If the value
being searched for is greater than the highest value it will return the complement of the Count.
Array has similar behavior, but it is a static method in that case.
-----
So I had a thought.
Since all of your data is Integer data, you can search for a double that lies between consecutive
ints (say target + 0.1). You will NEVER get an exact match, so you will always get the next greater
value.
"Aren't I clever", I though.
But it didn't quite work out as I planned.
ArrayList(and int[] for that matter) didn't like mixing and matching boxed Int32s and Doubles.
So I played and came up with a few workarounds.
1. If you used a double[] for your collection it would work.
2. If you Forced your Ints to be stored as doubles in the ArrayList via a cast it should
work(untested)
3. Use a custom IComparer for the job...It looks like this:
public class MyComparer:IComparer
{
public int Compare(object obj1, object obj2)
{
double a = Convert.ToDouble(obj1);
double b = Convert.ToDouble(obj2);
return a.CompareTo(b);
}
}
I had to use Convert.ToDouble() rather than (double) because although this is OK
int n =2;
double d = 3.14;
int x = (int) d; // x == 3
double a = (double)n; a == 2.0
You CANNOT cast a boxed Int32 to a double or a boxed double to an Int32.
Ugh...The joy of boxing.
Sooo.....
Assuming you have an ArrayList list filled with boxed ints you can search as follows
int target = 7;
MyComparer myComparer = new MyComparer();
// negidx is the compement of the index that we want
int negidx = list.BinarySearch(target + .1, myComparer);
int idx = ~negidx;
Here is a little program (with very liitle exception saftey) to demonstrate
Good luck
Bill
---------------------------------
using System;
using System.Collections;
class Test
{
private static string prompt = "Enter target integer (ENTER to exit):";
public static void Main()
{
ArrayList list = new ArrayList();
for(int i = 0; i < 100; i++)
list.Add(i/2);
for(int i = 0; i < list.Count; i++)
Console.WriteLine("[{0,2}]:{1}",i, list
);
MyComparer myComparer = new MyComparer();
Console.WriteLine("------------------------");
Console.WriteLine(prompt);
string input = Console.ReadLine();
while(input != "")
{
double target = Convert.ToInt32(input) + .1;
int negidx = list.BinarySearch(target + .1, myComparer);
int idx = ~negidx;
if(idx == list.Count)
Console.WriteLine("Too Big, try a smaller number");
else
Console.WriteLine("idx:{0} negidx:{1} Value:{2}",idx,negidx, list[idx]);
Console.WriteLine(prompt);
input = Console.ReadLine();
}
Console.WriteLine("Bye");
}
}
public class MyComparer:IComparer
{
public int Compare(object obj1, object obj2)
{
double a = Convert.ToDouble(obj1);
double b = Convert.ToDouble(obj2);
return a.CompareTo(b);
}
}