#1
  1. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    9
    Rep Power
    0

    Binary search in a 2d


    hi,

    i'm new to programming and i have an assignment i can't figure out.

    i need to determine if an integer is in a 2d array of N*N. the array is sorted:
    90 92 93 99
    23 57 76 80
    1 4 6 9
    and the time complexity has to be O(log(n)).

    HOW?

    thanks lol
  2. #2
  3. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    Do the rows overlap at all?

    Given
    A x x x B
    C x x x D
    E x x x F
    B is always > C
    D is always > E

    And A C E is always sorted as well?

    Then it's a binary search to find the row, then another binary search within the row.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  4. #3
  5. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    9
    Rep Power
    0
    hi,

    yes everything is perfectly sorted :)

    and still, how do i preform the search?

    sorry if it seems like a dumb question...
  6. #4
  7. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    Well if it were me, I'd use the bsearch library function.

    But I'm going to guess that it's your homework to implement a bsearch, so I'd say start with typing "binary search" into a search engine, and doing a bit of reading.
    Say perhaps the Wikipedia entry for a start.

    Try and implement something simple, like a bsearch on a 1D array and post back when you have code (and are stuck).
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  8. #5
  9. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    9
    Rep Power
    0
    ok so i've been able to write some piece of code. everything works excapt for the number 54. any explanation?
    Code:
    #define N 6 /*the number of rows and columns and in the matrix*/
    /*-------------------------------------------------------------------------
    the function will recive a sorted matrix(a matrix in which the numbers in each row are greater then the previous row and greater then the numbers before them) and will check if a searched number is there.
     -------------------------------------------------------------------------*/
    int search_matrix(int a[N][N], int x);
    
    int main()
    {
    int x,rc;
    int matrix[N][N]={{93,94,96,97,99,104},{75,80,81,82,85,87},{54,65,66,68,70,73},{35,37,38,40,43,50},{14,16,19,20,31,33},{3,4,7,8,10,12}};
    printf("Hi, This will help you search an integer in a matrix\nPlease enter an integer:\n");
    rc=scanf("%d",&x);
    if(rc!=1)
    {
        printf("Error!You didn't enter an integer!\n");
        return 1;
        }
    printf("The result is %d\n",search_matrix(matrix,x));
    return 0;
        }
    
    int search_matrix(int a[N][N], int x)
    {
        int mid ,max=0,min=N-1,row;
        while (max <= min)
        {
            mid=(max+min)/2;
            if(x<a[N-1][0])
            {
                row=N-1;
                break;
                }
            else if (x<=a[mid][0])
                {
                   max = mid;
                   if (x > a[mid+1][0])
                   {
                   row=mid+1;
                   break;
                    }
                   if (x == a[mid+1][0])
                   {
                   row=mid+1;
                   break;
                    }
                }
            else if (x>=a[mid][0])
            {
                min = mid;
                if (x < a[mid-1][0])
                   {
                   row=mid;
                   break;
                    }
                if (x == a[mid-1][0])
                   {
                   row=mid-1;
                   break;
                    }
                }
        }
        max=N-1;
        min=0;
        printf("%d\n",row);
        while (max >= min)
        {
            mid=(max+min)/2;
          if(a[row][mid]<x)
            min = mid + 1;
          else if(a[row][mid] > x )
            max = mid - 1;
          else if(a[row][mid]==x)
            return 1;
        }
      return 0;
        }
  10. #6
  11. Contributed User
    Devshed Specialist (4000 - 4499 posts)

    Join Date
    Jun 2005
    Posts
    4,392
    Rep Power
    1871
    > everything works excapt for the number 54. any explanation?
    a) add some prints to the code, like
    Code:
        mid = (max + min) / 2;
        printf("Max=%d, Min=%d, mid=%d\n", max, min, mid );
    If you put similar 'debug' printf statements through the code, you can work out the path that it takes.

    b) Use a debugger, set a breakpoint on search_matrix, then single-step through the code. When the code jumps to somewhere you don't expect, or a variable has an unexpected value, you've found a bug!

    I do know that if you enter 54, you end up searching the wrong row of the matrix.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper
  12. #7
  13. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2013
    Posts
    9
    Rep Power
    0
    thanks!

IMN logo majestic logo threadwatch logo seochat tools logo