C#面试题： 寻找中间值

给定一个数组，在区间内从左到右查找中间值，每次查找最小值与最大值区间内的中间值，且这个区间元素数量不小于3。

例如

1.给定数组float[] data = { 1, 2.3f, 4, 5.75f, 8.125f, 10.5f, 13, 15, 20 }

输出：10.5、5.75、4、2.3、8.125、15、13

解释：

1）（20+1）/2=10.5，首先从整个数组中获取中间值；

2）（10.5+1）/2=5.75，从左边开始计算，左边为1，也就是区间[1,10.5]，此区间元素数量大于2，因此需要计算；

3）（1+5.75）/2=3.375，左边为1，也就是区间[1,5.75]，此区间元素数量大于2，因此需要计算；数组中不存在3.375，找最接近的4；

4）（1+4）/2=2.5，，左边为1，也就是区间[1,4]，此区间元素数量大于2，因此需要计算；数组中不存在2.5，找最接近的2.3；

左边查找结束，查找右边

5）（5.75+10.5）/2=8.125，区间[5.75，10.5]，此区间元素数量大于2，因此需要计算；

6）8.125与10.5，区间[8.125，10.5]，此区间元素数量等于2，因此不需要计算；

7）（10.5+20 ）/2=15.25，区间[10.5，20]，此区间元素数量大于2，因此需要计算；数组中不存在，找最接近的15

8）（10.5+15）/2=12.75，先找左边区间，区间[10.5，15]，此区间元素数量大于2，因此需要计算；数组中不存在，找最接近的13

9）15与20之间无，结束。

2.给定数组float[] data = { 1, 2, 3, 4, 5, 6, 7, 8, 9 }

输出：5、3、2、4、7、6、8

代码：

 public static Queue<float> FindMiddle(float[] data){if (data.Length < 3) return new Queue<float>();int leftIndex = 0;int rightIndex = data.Length - 1;Queue<float> queue = new Queue<float>(data.Length - 2);FindMiddle(data, leftIndex, rightIndex, queue);return queue;}static void FindMiddle(float[] data, int leftIndex, int rightIndex, Queue<float> queue){if (rightIndex - 1 <= leftIndex) return;float target = (data[leftIndex] + data[rightIndex]) / 2f;int middleIndex = FindClosestNum(data, leftIndex, rightIndex, target, out float value);queue.Enqueue(value);FindMiddle(data, leftIndex, middleIndex, queue);FindMiddle(data, middleIndex, rightIndex, queue);}static int FindClosestNum(float[] nums, int leftIndex, int rightIndex, float target, out float middle){int left = leftIndex;int right = rightIndex;int mid = 0;float temp;while (left <= right){mid = left + ((right - left) >> 1);temp = nums[mid];if (temp == target){middle = temp;return mid;}else if (temp < target)left = mid + 1;elseright = mid - 1;}if (right < 0){middle = nums[left];return left;}else if (left >= nums.Length){middle = nums[right];return right;}else{if (Math.Abs(nums[left] - target) < Math.Abs(nums[right] - target)){middle = nums[left];return left;}else{middle = nums[right];return right;}}}

思路：从左边查找中间值，直到找完后找右边，一直到结束