1

我的目标是只对二维数组中的第一个元素执行二进制搜索。我整天都在寻找是否可以在 .NET 中使用 BinarySearch() 但我找不到任何东西。

为了更清楚地说明这一点。想象一下，我有一个未排序的一维数组。如果我对数组进行排序，我会丢失原始索引。我想创建数组的第二个元素来保存原始索引（我可以这样做），然后按第一个元素排序，然后对第一个元素进行二进制搜索。

如果有人能把我推向正确的方向，我将不胜感激。谢谢

4

4 回答 4

3

好吧，如果我理解正确的话，你需要这样的东西：

// initialize the array and the indexes array
var a2D = new int[2][];
a2D[0] = new[] { 3, 14, 15, 92, 65, 35 }; // <-- your array (fake data here)
a2D[1] = Enumerable.Range(0, a2D[0].Length).ToArray(); // create the indexes row

// sort the first row and the second one containing the indexes
Array.Sort(a2D[0], a2D[1]);

// now a2D array contains:
//  row 0: 3, 14, 15, 35, 65, 92
//  row 1: 0,  1,  2,  5,  4,  3

// and you can perform binary search on the first row:
int columnIndexOf35 = Array.BinarySearch(a2D[0], 35);
// columnIndexOf35 = 3
// 
// a2D[0][columnIndexOf35] = 35 <- value
// a2D[1][columnIndexOf35] = 5  <- original index
于 2012-08-06T15:57:06.873 回答
1

根据MSDN，Array.BinarySearch方法仅对一维数组进行操作，因此在您的情况下无法直接使用它。您拥有的一些选项是：

  1. 将第一列提取到一个单独的数组中并调用Array.BinarySearch它。
  2. 定义实现接口的自定义类 PairIComparable并使用此类的实例构造您的数组。
  3. 自己实现二维数组的二分查找。
于 2012-08-06T15:45:16.333 回答
0

根据您之后计划对数组执行的操作，另一种解决方案可能是使用 LINQ。

var unsortedStartingArray = new[] {3, 6, 2, 1, 20, 20};
var q = unsortedStartingArray
        .Select((item, index) => new {item, index})
        .ToLookup(x => x.item, x => x.index);

var notFound = q[30]; // An empty array. Nothing found
var indexOf1 = q[1].First(); // returns 3
var multipleIndexsOf20 = q[20]; // Returns an array with 4, 5

查找的索引将是您正在搜索的值。性能方面，我估计这比我的粗略测试要快约 5 倍。

于 2012-08-06T17:02:35.417 回答
0

看起来您想要拥有包含数据和“原始索引”的对象，而不是按数据排序/搜索对象数组。

（这个答案显示了安德烈的选项 2）

class IndexedData:IComparable
{
  public MyType Data;
  public int OriginalIndex;

  public int CompareTo(object obj) {
    // add correct checks for null,.. here
    // and return correct comparison result. 
    // I.e. if MyType is IComparable - just delegate.
    return Data.CompareTo(obj);
}

检查MSDN 上的IComparable以了解实现/使用细节。

于 2012-08-06T15:50:57.170 回答