binary search

This is a discussion on binary search within the C Programming forums, part of the General Programming Boards category; Does anyone know how I could search a 2D array using binary search and if so explain each part of ...

  1. #1
    Registered User
    Join Date
    Sep 2003
    Posts
    19

    binary search

    Does anyone know how I could search a 2D array using binary search and if so explain each part of the code for me? I would appreciate it very much. Thank you!

  2. #2
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    It depends on how the data is being sorted in the array. Might be helpful to show the code the fills the array.

  3. #3
    Registered User Codeplug's Avatar
    Join Date
    Mar 2003
    Posts
    4,630
    search: binary search

    gg

  4. #4
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,157
    What is the order of the array's contents? Binary sorts are only good with sorted lists AFAI Remember
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  5. #5
    & the hat of GPL slaying Thantos's Avatar
    Join Date
    Sep 2001
    Posts
    5,681
    You are correct WaltP. Binary search is useless in an unsorted array. Heck I'd venture to guess that any searching method, besides stepping through each item one by one, would not work on an unsorted array.

  6. #6
    Registered User
    Join Date
    Sep 2003
    Posts
    19
    Sorry about that guys. It feels the array with random characters that are already sorted alphabetically be the first character.

    Code:
    char *RandomString(int length){
    
      int i, size;
      char *string;
    
      size = 1 + rand() % length;
    
      string = calloc(size + 1, sizeof(char));
    
      for(i = 0; i < size; i++){
        string[i] = (char)((rand() % 26) + 65);
      }
      string[i] = '\0';
    
      return string;
    
    }

  7. #7
    Registered User
    Join Date
    Sep 2003
    Posts
    19
    It is still pretty early for me, I apologize about the english. What I meant to say is that the code fills the array with random capital letters that are already sorted alphabetically by the first character and length.

  8. #8
    Code Goddess Prelude's Avatar
    Join Date
    Sep 2001
    Posts
    9,796
    A multidimensional array when passed to a function is simply a pointer to the first element. Because multidimensional arrays are actually stored in memory as a large single dimensional array, you can treat them exactly the same in your search routine as long as you get the sizes right.

    Warning: An example follows
    Code:
    #include <stdio.h>
    #include <stdlib.h>
    
    int cmp ( const void *a, const void *b )
    {
      int aa = *(int*)a;
      int bb = *(int*)b;
    
      if ( aa < bb )
        return -1;
      else if ( aa > bb )
        return +1;
      else
        return 0;
    }
    
    int main( void )
    {
      int values[][4] = { 
        { 1, 2, 3, 4 },
        { 5, 6, 7, 8 },
      };
      int *found;
      int key = 7;
    
      found = bsearch ( &key, values, 8, sizeof ( int ), cmp );
      if ( found != NULL )
        printf ( "%d is in the array\n", *found );
      else
        printf ( "%d is not in the array\n", key );
    
      return 0;
    }
    My best code is written with the delete key.

  9. #9
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,157

    Re: binary search

    Originally posted by chauncey005 on 12-03-2003
    Does anyone know how I could search a 2D array using binary search and if so explain each part of the code for me? I would appreciate it very much. Thank you!
    Originally posted by chauncey005 on 12-04-2003
    Sorry about that guys. It feels the array with random characters that are already sorted alphabetically be the first character.

    Code:
    char *RandomString(int length){
    
      int i, size;
      char *string;
    
      size = 1 + rand() % length;
    
      string = calloc(size + 1, sizeof(char));
    
      for(i = 0; i < size; i++){
        string[i] = (char)((rand() % 26) + 65);
      }
      string[i] = '\0';
    
      return string;
    
    }
    Originally you mention 2D which is a matrix, i.e buffer[x][y]. Then you show code that loads a 1D array, i.e buffer[x]. So which is it? If it's 2D, it depends on how the buffer is loaded (row first or column first). 1D doesn't matter, if it's sorted, it's obvious.
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

  10. #10
    Registered User
    Join Date
    Sep 2003
    Posts
    19
    My apologies Walt, its a 1D array. What I was meaning to say is that I have an array of the number of random strings assigned and inside the indexes actually list the random strings themselves. I hope I have made it a little more clear. Thanks again!

  11. #11
    Been here, done that.
    Join Date
    May 2003
    Posts
    1,157
    Originally posted by chauncey005
    My apologies Walt, its a 1D array. What I was meaning to say is that I have an array of the number of random strings assigned and inside the indexes actually list the random strings themselves. I hope I have made it a little more clear. Thanks again!
    In that case, it's simple. Assume there are n entries in the list.

    Code:
    first = 0
    last = n-1
    num = n/2
    
    loop
    {
        test array[first + num)]
        if array[t] < target last = num
        if array[t] > target first = num
        num = num/2
    }
    Something like that wil be close.
    Definition: Politics -- Latin, from
    poly meaning many and
    tics meaning blood sucking parasites
    -- Tom Smothers

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. searching and insertion in a binary search tree
    By galmca in forum C Programming
    Replies: 1
    Last Post: 03-26-2005, 04:15 PM
  2. deleting all nodes of a binary search tree...
    By sachitha in forum C++ Programming
    Replies: 3
    Last Post: 09-29-2004, 06:19 AM
  3. Tutorial review
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 11
    Last Post: 03-22-2004, 08:40 PM
  4. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21