前提：我的区间是用[,)计算的，集合已经升序排列好了。
/// <summary> /// /// </summary> /// <param name="data"></param> /// <param name="list"></param> /// <param name="low"></param> /// <param name="high"></param> /// <param name="left"></param> /// <param name="right"></param> /// <returns></returns> public static Tuple<int, int> BinarySearchRecursive(int data, IEnumerable<int> list, int low, int high, Tuple<int, int> left, Tuple<int, int> right) { int mid = (high + low) / 2; if (data >= left.Item2 && data <= right.Item2 && (right.Item1 - left.Item1 == 1)) { return new Tuple<int, int>(left.Item2, right.Item2); } if (data >= list.ElementAt(list.Count() - 1)) { //右边界 return new Tuple<int, int>(list.ElementAt(list.Count() - 1), int.MaxValue); } if (data < list.ElementAt(0)) { //左边界 return new Tuple<int, int>(int.MinValue, list.ElementAt(0)); } if (list.ElementAt(mid) > data) { return BinarySearchRecursive(data, list, low, mid - 1, left, new Tuple<int, int>(mid, list.ElementAt(mid))); } else if (list.ElementAt(mid) < data) { return BinarySearchRecursive(data, list, mid + 1, high, new Tuple<int, int>(mid, list.ElementAt(mid)), right); } //恰好和数组元素匹配的处理 return new Tuple<int, int>(list.ElementAt(mid), list.ElementAt(mid + 1)); }
有点恶心。不过测试通过就好啦。得到区间后其余就容易了，不过这个方法调用的时候有特别的技巧。那是作为递归结束的条件而特别那样的。
static void Main(string[] args)
{
//var list = new List<int>() { 0, 50, 60, 80, 100 };
var list = new List<int>() { 0, 50, 60, 800, 999 };
Random r = new Random();
int s = -50;
var v = Class1.BinarySearchRecursive(s, list, 0, list.Count, new Tuple<int, int>(1, int.MaxValue), new Tuple<int, int>(0, int.MinValue));
Console.WriteLine("随机数:{0}区间[{1},{2})", s, v.Item1, v.Item2);
s = 0;
v = Class1.BinarySearchRecursive(s, list, 0, list.Count, new Tuple<int, int>(1, int.MaxValue), new Tuple<int, int>(0, int.MinValue));
Console.WriteLine("随机数:{0}区间[{1},{2})", s, v.Item1, v.Item2);
s = 50;
v = Class1.BinarySearchRecursive(s, list, 0, list.Count, new Tuple<int, int>(1, int.MaxValue), new Tuple<int, int>(0, int.MinValue));
Console.WriteLine("随机数:{0}区间[{1},{2})", s, v.Item1, v.Item2);
s = 88;
v = Class1.BinarySearchRecursive(s, list, 0, list.Count, new Tuple<int, int>(1, int.MaxValue), new Tuple<int, int>(0, int.MinValue));
Console.WriteLine("随机数:{0}区间[{1},{2})", s, v.Item1, v.Item2);
s = 999;
v = Class1.BinarySearchRecursive(s, list, 0, list.Count, new Tuple<int, int>(1, int.MaxValue), new Tuple<int, int>(0, int.MinValue));
Console.WriteLine("随机数:{0}区间[{1},{2})", s, v.Item1, v.Item2);
s = 1000;
v = Class1.BinarySearchRecursive(s, list, 0, list.Count, new Tuple<int, int>(1, int.MaxValue), new Tuple<int, int>(0, int.MinValue));
Console.WriteLine("随机数:{0}区间[{1},{2})", s, v.Item1, v.Item2);
for (int i = 0; i < 50; i++)
{
var a = r.Next(-50, 1200);
v = Class1.BinarySearchRecursive(a, list, 0, list.Count, new Tuple<int, int>(1, int.MaxValue), new Tuple<int, int>(0, int.MinValue));
Console.WriteLine("随机数:{0}区间[{1},{2})", a, v.Item1, v.Item2);
}
Console.ReadKey();
}
写的比较水，但是总结一下递归的要点应该就是把一些结果作为参数回传自身，收束的条件能够清晰的话，那问题就迎刃而解了。在这里我收束的条件是：这个数值>left并且<right并且left和right索引的差为1