Finding lower_bound() of a column in a 2D array

Question

I have a 2D array, in which I want to find the lower bound in a particular column.

How can I do that using std::lower_bound?

Answer 1

As some answers have already told how to do it,I suggest making our own lower bound function for columns using binary search.

 int lowerboundforcols(int target,int a[][m],int index)
 {
 //m are number of columns
 //and index here is the index of the column for which you are searching.
 int lo=0;int hi=n-1,ans=-1;
      while(lo<=hi)
        {
          int mid=lo+(hi-lo)/2;
          if(a[mid][index]<target)
          {
            lo=mid+1;
          }
          else{hi=mid-1;ans=mid;}
          //because if there are duplicate 'target' and we want to  
          //find the first one.  
        }
        return ans;
        //returns -1 if there is no number greater than or equal to target
        //in column,else return the first (0-based)index.
 }

Answer 2

Just use this function:

vector<unsigned> column_lower_bound(const vector<vector<unsigned> >& matrix) {
    size_t rows = matrix.size(), columns = matrix[0].size();
    vector<unsigned> result(columns, ~0);

    for(size_t y = 0; y < rows; y++) {
        const vector<int>& curRow = matrix[y];
        assert(curRow.size() == columns);

        for(size_t x = 0; x < columns; x++) {
            if(result[x] > curRow[x]) result[x] = curRow[x];
        }
    }
    return result;
}

Or something similar. Make it a template if you must.

---

Just for interest, here is the C variant:

void column_lower_bound(size_t width, size_t height, unsigned (*matrix)[width], unsigned* result) {
    for(size_t x = 0; x < width; x++) result[x] = ~0;

    for(size_t y = 0; y < rows; y++) {
        unsigned* curRow = matrix[y];
        for(size_t x = 0; x < columns; x++) {
            if(result[x] > curRow[x]) result[x] = curRow[x];
        }
    }
}

This won't work in C++, because you can't use 2D arrays with a runtime size in C++. C is much more flexible in that respect.

Answer 3

Introduction

This is not as hard as one might think it is, let us first walk through the abstract of algorithm functions that apply to ranges.

Every such function, like std::lower_bound, accepts a begin and an end iterator to know which elements they are going to search. The problem in our case as it seems non-trivial to create an iterator that iterates over columns, instead of rows.

The good news; it isn't.

---

Forming a pointer to array

We can create pointers to pretty much anything in C++, and that certainly include arrays.

What's good with pointers is that if we increment one we will get to the next element, no matter what type the pointer is referring to. In our case we'd like to iterate over all the nested arrays in our 2D array.

T a[5][3] = { ... };

T(*p)[3] = &a[0]; // is a pointer to an array of three `T`,
                  // currently pointing to a[0]

++p;              // now referring to a[1]

---

The implementation

#include <iostream>
#include <algorithm>
#include <iterator>

struct not_less_than_column {
  not_less_than_column (unsigned long idx)
    : m_idx (idx)
  { }

  template<class T, unsigned long N>
  bool operator() (T(&arr)[N], T const& needle) const {
    return arr[m_idx] < needle;
  }

  unsigned long m_idx;
};

int main () {
  int a[5][3] = {
    { 0, 24,  1 },
    { 0, 35,  1 },
    { 0, 42,  1 },
    { 0, 66,  1 },
    { 0, 100, 1 }
  };

  auto ptr = std::lower_bound (std::begin (a), std::end (a), 36, not_less_than_column (1));

  for (auto const& e : *ptr)
    std::cout << e << " "; // 0 42 1
}

<sup>Note: Using std::begin and std::end is an clearer alterantive to &a[0] and &a[5].

Note: We could replace not_less_than_column(1) with a lambda, but since generic lambdas are not supported in C++11 the current approach is cleaner.</sup>

Answer 4

You could try and write an iterator for columns:

template<typename T , std::size_t ROWS , std::size_t COLUMNS>
class column_iterator
{
    std::size_t _row; //Current position of the iterator
    const std::size_t _column; //The column which the iterator traverses

    T& _array[ROWS][COLUMNS]; //Reference to the array

public:
    column_iterator( T (&array[ROWS][COLUMNS]) , std::size_t column , std::size_t pos = 0) :
        _array{ array } , 
        _row{ pos } ,
        _column{ column }
    {}

    const T& operator*() const
    {
        return _array[_row][_column];
    }

    T& operator*()
    {
        return _array[_row][_column];
    }

    column_iterator& operator++()
    {
        _row++;

        return *this;
    }

    friend bool operator==( const column_iterator& lhs , const column_iterator& rhs )
    {
        return lhs._row == rhs._row && lhs._column == rhs._column;
    }
};

Also you could write a factory function to make the creation of such iterators easy:

template<typename T , std::size_t ROWS , std::size_t COLUMNS>
column_iterator<T,ROWS,COLUMNS> iterate_column( T (&array[ROWS][COLUMNS]) , std::size_t column , std::size_t row = 0 )
{
    return column_iterator<T,ROWS,COLUMNS>{ array , row , column };
}

And use it as follows:

int main()
{
    int foo[2][2] = { {1,2} , 
                      {3,4} };

    auto iterator = iterate_column( foo , 0 );
}

Or even:

template<typename T , std::size_t ROWS , std::size_t COLUMNS>
column_iterator<T,ROWS,COLUMNS> column_begin( T (&array[ROWS][COLUMNS]) , std::size_t column )
{
    return iterate_column( array , column , 0 );
}

template<typename T , std::size_t ROWS , std::size_t COLUMNS>
column_iterator<T,ROWS,COLUMNS> column_end( T (&array[ROWS][COLUMNS]) , std::size_t column )
{
    return iterate_column( array , column , ROWS );
}

And then:

std::lower_bound( column_begin( foo , 1 ) , column_end( foo , 1 ) , 2 );

Which (If I have implemented this correctly) should return 2

Answer 5

The simple answer to just stick the column identification into the predicate and use the iterator of the outer array. This assumes a two dimensional array which has enough columns in each row, though. Of course, making sure that array isn't ragged is easy for built-in arrays:

#include <algorithm>
#include <iostream>

int main()
{
    int array[][3] = {
        {  1,  2,  3 },
        {  4,  5,  6 },
        {  7,  8,  9 },
        { 10, 11, 12 }
    };

    for (int column(0); column < 3; ++ column) {
        int (*lower)[3] = std::lower_bound(std::begin(array), std::end(array),
                                           6, [=](int (&ptr)[3], int value){
                                               return ptr[column] < value; });
        std::cout << "column=" << column << " row=" << (lower - array) << "\n";
    }
}