I've been working of the find (problem set 3) for 2 weeks and I'm just stuck.
I already have the design etc worked out but there is a bug that I seem to be missing.
So the problem is that when I run it through the check (check50 2015.fall.pset3.find helpers.c) I keep getting this:
I also checked the printout of my own error messages which showed me that something was wrong, although I don't exactly understand why, it seems that the program only finds the needle if it is the first of the array... which doesn't make any sense to me at all.
For example - this works (sorting clearly works) ./find 42 haystack[0] = 43 haystack1 = 44 haystack[2] = 42 haystack[3] = (cancelled here) - 43 44 42 - 43 42 44 - 43 42 0 - 42 43 0 - 42 0 43 - 42 0 43 - 0 42 43 - 0 42 43 - 0 42 43 - 0 42 43 - 0 42 43 - 0 42 43 - 0 42 43 - 42 Found needle in haystack!
But this doesn't: ./find 42 haystack[0] = 40 haystack1 = 43 haystack[2] = 42 haystack[3] = (canceled here) - 40 43 42 - 40 42 43 - 40 42 0 - 40 42 0 - 40 0 42 - 40 0 42 - 0 40 42 - 0 40 42 - 0 40 42 - 0 40 42 - 0 40 42 - 0 40 42 - 0 40 42 - 40 - 40 upper half - Bug40 mid value - first 2 last 2 mid 1 Didn't find needle in haystack.
Here is my helpers.c file for reference - I have printf statements throughout as I find it more convenient that the GBD. /** * helpers.c * * Computer Science 50 * Problem Set 3 * * Helper functions for Problem Set 3. */
#include <cs50.h>
#include <stdio.h>
#include "helpers.h"
/**
* Returns true if value is in array of n values, else false.
*/
//function declaration
void swap(int *a, int *b);
void sort(int values[], int n);
bool search(int value, int values[], int n)
{
//intialize variables to calculate mid
int first = 0;
int last = n - 1; //array is zero indexed TODO Check if this is correct
int evencheck = (first + last);
//to ensure mid rounds up to the nearest whole number
if (evencheck%2 > 0)
{
evencheck++;
}
int mid = (evencheck/2);
while (first < last)
{
int check = mid;
if (value == values[mid])
{
//my check
for (int s = 0; s < n; s++)
{
printf("%d ", values[s]);
}
printf("\n");
printf("%d\n", values[mid] );
return true;
break;
}
else if (value < values[mid])
{
//search in lower half
//my check
for (int s = 0; s < n; s++)
{
printf("%d ", values[s]);
}
printf("\n");
printf("%d lower half \n", values[mid] );
last = mid - 1;
printf("%d lower half \n", values[mid] );
}
else if (value > values[mid])
{
//search in upper half
//my check
for (int s = 0; s < n; s++)
{
printf("%d ", values[s]);
}
printf("\n");
printf("%d\n", values[mid] );
first = mid + 1;
printf("%d upper half \n", values[mid] );
}
int count = 0;
//if needle not found
if (check == mid)
{
count++;
}
if (count > 1)
{
return false;
break;
}
}
//to fix end of non-void function
printf("Bug");
printf("%d mid value \n", values[mid] );
printf("first %d last %d mid %d \n", first, last, mid );
return false;
}
//sorting fxn
void sort(int values[], int n)
{
// Bubble sort
bool sorted = false;
//find the smallest number
do
{
//swap according to value of number (smallest to greatest) as long as unsorted
sorted = true;
for (int i = 0; i < n; i++)
{
if (values[i] > values[i+1])
{
swap(&values[i], &values[i+1]);
sorted = false;
}
//my check
for (int s = 0; s < n; s++)
{
printf("%d ", values[s]);
}
printf("\n");
}
}
//as long as there is one swap, sorted will be false & program will iteratee.
while (sorted == false);
return; // when the final pass is done
}
//swapping fxn
void swap(int *a, int *b)
{
int temp = *a;
*a = *b;
*b = temp;
}
