Binary Search on the first element in a multiple dimensional array

Question

My goal is to perform a binary search for only the first element in a 2D array. I have been searching all day to find if it is possible using BinarySearch() in .NET but I can't find a thing.

To make this clearer. Imagine I had a 1D array, unsorted. If I sort the array, I lose the original index. I would like to create a second element of my array to hold the original index (this I can do) then sort by first element, then binary search over the first elements.

If anyone could push me in the right direction I'd be very grateful. Thanks

I don't fully get you... could you please provide a small numeric example ? — digEmAll
– digEmAll, Commented Aug 6, 2012 at 15:34
Thanks for quick response :) Imagine I had the following: { [400,0] , [333,1], [967, 2], [723,3] } Sorting by the first element I get: { [333,1], [400,0] , [723,3], [967, 2] } I can now attempt to do a binary search over the first elements: 333, 400, 723, 967 But I don't know how. — John M
– John M, Commented Aug 6, 2012 at 15:47

digEmAll · Accepted Answer · 2012-08-06 16:22:55Z

3

Well, if I understand you correctly, you need something like this:

// 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

edited Aug 6, 2012 at 16:22

answered Aug 6, 2012 at 15:57

digEmAll

57.4k9 gold badges118 silver badges142 bronze badges

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

1 Comment

Alexei Levenkov Over a year ago

+1. This is exact answer - did not know this version of Sort exists. See Array.Sort for info.

Andrei · Accepted Answer · 2012-08-06 15:45:16Z

1

As per MSDN, Array.BinarySearch method operates only with one-dimensional arrays, so it is impossible to use it directly in your case. Some of the options you have are:

Extract first column into a separate array and call Array.BinarySearch on it.
Define custom class Pair that implements interface IComparable and construct your array with the instances of this class.
Implement binary search on two dimensional array by yourself.

answered Aug 6, 2012 at 15:45

Andrei

56.8k10 gold badges92 silver badges114 bronze badges

2 Comments

John M Over a year ago

Thanks for the quick response! The first method you advise I have done, but I cannot trace back the original index. I'll have to read up more on IComparable to have a go. Option 3 is where I'm heading, the source code doesn't look too difficult to implement an extra dimension that isn't used in the search. Was hoping it didn't come to that though!

Andrei Over a year ago

You can surely use the first option, but after all the manipulations you've described in the post. When you have sorted values in the first column and original index in the second, you can create new array out of the first column, then perform a binary search on it. The result is an index in the first column, and the corresponding element in the second column will give you the original index.

Alexei Levenkov · Accepted Answer · 2012-08-06 15:50:57Z

0

It looks like you want to have object that holds data and "original index" and than sort/search array of objects by data.

(This answer shows Andrei's option 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);
}

Check IComparable on MSDN for implementation/usage details.

answered Aug 6, 2012 at 15:50

Alexei Levenkov

101k15 gold badges138 silver badges189 bronze badges

1 Comment

John M Over a year ago

Thank you so much. This looks very promising!

Frank · Accepted Answer · 2012-08-06 17:12:07Z

0

Depending on what you're planning to do with the arrays afterwards, another solution might be to use 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

The index into the lookup would then be the value you're searching for. Performance wise I would guesstimate this to be ~~faster aswell~~ about 5 times slower from my crude testing.

edited Aug 6, 2012 at 17:12

answered Aug 6, 2012 at 17:02

Frank

4833 silver badges7 bronze badges

Collectives™ on Stack Overflow

Binary Search on the first element in a multiple dimensional array

4 Answers 4

1 Comment

2 Comments

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

1 Comment

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related