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;
}