Page 1 of 2 12 Last
  • Jump to page:
    #1
  1. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,625
    Rep Power
    4247

    C Puzzle of the week/month/year (2009-12-08)


    Right guys, it is time for another puzzle of the week/month/year. Today's code is a simple binary search function written in C:
    Code:
    int binary_search(int *array, int target, int low, int high)
    {
        int middle; 
    
        if (low >= high)
            return 0;
    
        middle = (low + high) / 2;
    
        if (target == array[middle])
            return 1;
        else if (target < array[middle])
            return binary_search(array, target, low, middle);
        else
            return binary_search(array, target, middle + 1, high);
    }
    As you can see, the function looks for target within array. The assumptions made by this function are that array is already sorted and low and high are valid. There is however a serious bug in this function. Your task for this week is to (a) identify the bug and (b) propose a fix.

    Usual puzzle of the week rules apply: I'll post the solution on Friday, if no one has proposed the answer by then. As before, winners have the privilege of having their names appear in green font under my signature for an unspecified period of time.
    Last edited by Scorpions4ever; December 8th, 2009 at 07:08 PM.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  2. #2
  3. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    244
    This seems to work for me:

    Code:
    int binary_search(int *array, int target, int low, int high){
        int middle = ((low + high) / 2);; 
        if (low > high) return 0;
    
        if (target == array[middle])
            return 1;
        else if (target < array[middle])
            return binary_search(array, target, low, middle - 1);
        else
            return binary_search(array, target, middle + 1, high);
    }
    It appears that the low <= high was the problem as when it was equal it was failing to do the test.

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw
  4. #3
  5. Banned ;)
    Devshed Supreme Being (6500+ posts)

    Join Date
    Nov 2001
    Location
    Woodland Hills, Los Angeles County, California, USA
    Posts
    9,625
    Rep Power
    4247
    Not quite sir. To be fair, I edited my original code a bit and changed this line:
    Code:
        else if (target < array[middle])
            return binary_search(array, target, low, middle - 1);
    to:
    Code:
        else if (target < array[middle])
            return binary_search(array, target, low, middle);
    and the edit might have happened when you were looking at the code. If you have my correction, the if (low >= high) statement is correct.

    I'd originally swiped the code from a sample in dreamincode and the author had got it wrong ALONG with the bug I'm looking for. I corrected the one bug which was the one you pointed out. The other one is still there. It is actually very hard to get a decent binary search right.

    Here's a more generic version that has the same bug:
    Code:
    int binary_search(void *array, void *target, compare_fn compare, int elem_size, int low, int high)
    {
        int middle; 
        int cmp_result;
        void *ptr;
    
        if (low >= high)
            return 0;
    
        middle = (low + high) / 2;
    
        ptr = array + middle * elem_size;
        cmp_result = compare(target, ptr);
    
        if (cmp_result == 0)
            return 1;
        else if (cmp_result < 0)
          return binary_search(array, target, compare, elem_size, low, middle);
        else
          return binary_search(array, target, compare, elem_size, middle + 1, high);
    }
    and you can use it like this (for instance, to check entries in an array of int):
    Code:
    int compare_int(void *a, void *b) 
    {
      int x = *(int *)a;
      int y = *(int *)b;
      if (x < y)
        return -1;
      else if (x > y)
        return 1;
      return 0;
    }
    
    #define MAX_SIZE  10
    
    int main(void)
    {
      int array[MAX_SIZE];
      int i;
      int max_len = sizeof(array) / sizeof(array[0]);
      for (i = 0; i < MAX_SIZE; i++)
        array[i] = i + 1;
    
      for (i = 1; i < MAX_SIZE + 1; i++) {
        printf("Checking %d: %d\n", i, binary_search(array, &i, compare_int, sizeof(int), 0, max_len)); 
      }
    
      i = -1;
      printf("Checking %d: %d\n", i, binary_search(array, &i, compare_int, sizeof(int), 0, max_len)); 
      i = 42;
      printf("Checking %d: %d\n", i, binary_search(array, &i, compare_int, sizeof(int), 0, max_len)); 
       
      return 0;
    }
    This is a more generic version which can be used with arrays of any object. Can you spot the bug?

    [edit]Fixed the one typo (size / elem_size) pointed out below[/edit]
    Last edited by Scorpions4ever; December 9th, 2009 at 12:11 PM.
    Up the Irons
    What Would Jimi Do? Smash amps. Burn guitar. Take the groupies home.
    "Death Before Dishonour, my Friends!!" - Bruce D ickinson, Iron Maiden Aug 20, 2005 @ OzzFest
    Down with Sharon Osbourne

    "I wouldn't hire a butcher to fix my car. I also wouldn't hire a marketing firm to build my website." - Nilpo
  6. #4
  7. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Dec 2009
    Posts
    16
    Rep Power
    0
    is it change
    Code:
    middle = (high + low)/2;
    to
    Code:
    middle = low + (high - low)/2;
    due to overflow with large arrays?

    Comments on this post

    • mike65535 agrees : Nice
  8. #5
  9. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2009
    Posts
    337
    Rep Power
    46
    Is it overflow of (low + high)???
  10. #6
  11. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Originally Posted by scorpions4ever
    Here's a more generic version that has the same bug:
    It's not even compilable.

    binary_search(array, target, compare, size, low, middle);

    should probably be:

    binary_search(array, target, compare, elem_size, low, middle);

    I should probably know this, but does C allow doing arithmetic on void pointers? I had to change:

    ptr = array + middle * elem_size

    to:

    ptr = (void*)((char*)array + middle * elem_size);

    to get it to compile in my usual cpp file that I use for testing devshed stuff.

    I also had to add a typedef for compare_fn.
    Last edited by jwdonahue; December 9th, 2009 at 11:34 AM.
    I no longer wish to be associated with this site.
  12. #7
  13. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Originally Posted by Scorpions4ever
    Usual puzzle of the week rules apply
    Where can we find those?
    I no longer wish to be associated with this site.
  14. #8
  15. No Profile Picture
    Contributing User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jan 2009
    Posts
    337
    Rep Power
    46
    ptr = (void*)((int*)array + middle * elem_size);

    Shouldn't it be
    (char*) array + middle * elem_size
    ??
  16. #9
  17. No Profile Picture
    Contributing User
    Devshed Loyal (3000 - 3499 posts)

    Join Date
    May 2004
    Posts
    3,417
    Rep Power
    887
    Originally Posted by Nyan
    ptr = (void*)((int*)array + middle * elem_size);

    Shouldn't it be
    (char*) array + middle * elem_size
    ??
    Doh! I pasted the wrong line in there. Not thinking. I noticed elem_size was one of the factors and actually removed cast to int* from the function I was testing, but must have already had the other one in my clipboard. I initially had the first binary_search() in mind that only worked with ints. Thanks for catching that Nyan. I'll go edit the post.
    I no longer wish to be associated with this site.
  18. #10
  19. Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jun 2005
    Posts
    5,964
    Rep Power
    4852
    JW, how come you quoted me in post #6? Scorp and I are not the same person.
    Write no code whose complexity leaves you wondering what the hell you did.
    Politically Incorrect DaWei on Pointers Grumpy on Exceptions
  20. #11
  21. No Profile Picture
    Contributing User
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Jul 2004
    Location
    Middle Europa
    Posts
    1,200
    Rep Power
    14
    hallo scorpion
    i did NOT analized your code
    IMHO
    an 'else' after a 'if(..) return' is a STUPIDITY
    so
    Code:
               if(...) return(x);
               else buy caviar;
               return(0);
    that 'else' will never be reached if the 'if' statement is true, so :(:(:(
    Code:
                if(...) return(x);
                buy caviar;
                return(0);
    this is logic .... just a finesse!
    working on Solaris[5-9], preferred languages french and C.
  22. #12
  23. No Profile Picture
    Contributing User
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Jul 2004
    Location
    Middle Europa
    Posts
    1,200
    Rep Power
    14
    hallo scorpion and all other gurus in this forum
    ARE WE READY TO TEACH YOUNG PEOPLE
    to N O T repeat old stupidities, mistakes, or reinvent
    something like wheels, hammers and so on ?
    ++regards
    working on Solaris[5-9], preferred languages french and C.
  24. #13
  25. um, Hello?
    Devshed Novice (500 - 999 posts)

    Join Date
    Nov 2004
    Location
    FN23fc
    Posts
    719
    Rep Power
    160
    Code:
    middle = (low + high) / 2;
    "low + high" (before the divide-by-two is performed) can easily be bigger than an int. I think Nyan was indicating this.
    "America's abundance was created not by public sacrifices to "the common good," but by the productive genius
    of free men who pursued their own personal interests and the making of their own private fortunes. They did not
    starve the people to pay for America's industrialization. They gave the people better jobs, higher wages and
    cheaper goods with every new machine they invented, with every scientific discovery or technological advance --
    and thus the whole country was moving forward and profiting, not suffering, every step of the way."
    --Ayn Rand
  26. #14
  27. I'm Baaaaaaack!
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Jul 2003
    Location
    Maryland
    Posts
    5,538
    Rep Power
    244
    I am having problems getting buggy output. Any chance you can supply some sample data that triggers the bug or is that giving too much away?

    My blog, The Fount of Useless Information http://sol-biotech.com/wordpress/
    Free code: http://sol-biotech.com/code/.
    Secure Programming: http://sol-biotech.com/code/SecProgFAQ.html.
    Performance Programming: http://sol-biotech.com/code/PerformanceProgramming.html.
    LinkedIn Profile: http://www.linkedin.com/in/keithoxenrider

    It is not that old programmers are any smarter or code better, it is just that they have made the same stupid mistake so many times that it is second nature to fix it.
    --Me, I just made it up

    The reasonable man adapts himself to the world; the unreasonable one persists in trying to adapt the world to himself. Therefore, all progress depends on the unreasonable man.
    --George Bernard Shaw
  28. #15
  29. No Profile Picture
    Closet coder
    Devshed Beginner (1000 - 1499 posts)

    Join Date
    Feb 2005
    Location
    Plantation, FL <---south florida
    Posts
    1,431
    Rep Power
    153
    does low and high represent the the lowest and highest values in the array?

    so something like this would fail
    Code:
       int test_array[] = { 2, 5 };
       printf( "bool = %d", binary_search(test_array, 5, 2, 5));
    since middle in binary_search is finding the average between the values themselves and not the average of the array size? (2 elements, but we try to access array[3] for the comparison)
Page 1 of 2 12 Last
  • Jump to page:

IMN logo majestic logo threadwatch logo seochat tools logo