0

Somehow I am messing this up, I just can't figure out why. Sort works perfectly, as does my linear search function and they can pass Check50. However my implementation of binary search hasn't worked out as well. I admittedly need to study the algorithm more in-depth, but the code looks decent to me. When I run it with binary search the program will not ever even finish so I figure it's a simple execution error. Any help would be appreciated!

#include <cs50.h>
#include <stdio.h>
#include "helpers.h"

/*
* Returns true if value is in array of n values, else false.
* Linear search
* 
*/
/*

bool search(int value, int values[], int n)
    {
    if (n<0)
    {
    return false;
    }
    else
    { 
    for (int i=0; i<n; i++)
    {
        if (values[i]==value)
        {
            return true;
        }
    }
    return false;
}
}

 * Sorts array of n values.
 */
     bool search(int value, int values[], int n)
{
    if(n<0)
    {
        return false;
    }
    else
    {
        int small_index= 0;
        int high_index=n-1;
        int mid_index= (small_index + high_index)/2;
        while(small_index<=high_index)
        {
            if(values[mid_index]<value)
            {
              small_index= mid_index+1;  
            }
            else if(values[mid_index]==value)
            {
               return true;
            }
            else
            {
                high_index= mid_index-1;
            }

        }
        return false;
    }
}


void sort(int values[], int n)
{
    // counting sort
   int best[65536] = {0};
   for (int i=0; i<n; i++)
     {
        best[values[i]]++;
    }
    int hi=0;
    for (int j= 0; j<65536; j++)
    {
        if(best[j]>0)
        {
        for (int k=0; k< best[j]; k++)
        {
            values[hi]=j; 
            hi++;
        }
        }
    }
    for(int l=0; l<n; l++)
    {
        printf("%i ", values[l]);
    }
        printf("\n");
        return;
        }

1 Answer 1

1

Hmmm.... infinite loop problem. Looked at the code. Small_index gets reset nicely on each pass through the while loop. High_index gets reset nicely too.

So, after the low or high limit gets recalculated, where does the midpoint between them get recalculated?

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • Wow! I'm embarrassed it was that simple! Thanks for the help I just completed Find and now I understand binary search a lot better. I'm only about two months into CompSci so I hope I can keep improving from these silly errors.
    – Justin
    Jun 26, 2017 at 15:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .