find.c

/**
 * Prompts user for as many as MAX values until EOF is reached,
 * then proceeds to search that "haystack" of values for given needle.
 *
 * Usage: ./find needle
 *
 * where needle is the value to find in a haystack of values
 */

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

#include "helpers.h"

// maximum amount of hay
const int MAX = 65536;

int main(int argc, string argv[])
{
    // ensure proper usage
    if (argc != 2)
    {
        printf("Usage: ./find needle\n");
        return -1;
    }

    // remember needle
    int needle = atoi(argv[1]);

    // fill haystack
    int size;
    int haystack[MAX];
    for (size = 0; size < MAX; size++)
    {
        // wait for hay until EOF
        printf("\nhaystack[%i] = ", size);
        int straw = get_int();
        if (straw == INT_MAX)
        {
            break;
        }

        // add hay to stack
        haystack[size] = straw;
    }
    printf("\n");

    // sort the haystack
    sort(haystack, size);

    // try to find needle in haystack
    if (search(needle, haystack, size))
    {
        printf("\nFound needle in haystack!\n\n");
        return 0;
    }
    else
    {
        printf("\nDidn't find needle in haystack.\n\n");
        return 1;
    }
}

generate.c

/**
 * generate.c
 *
 * Generates pseudorandom numbers in [0,MAX), one per line.
 *
 * Usage: generate n [s]
 *
 * where n is number of pseudorandom numbers to print
 * and s is an optional seed
 */

#define _XOPEN_SOURCE

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// upper limit on range of integers that can be generated
#define LIMIT 65536

int main(int argc, string argv[])
{
    // Ensure the correct number of arguments are entered.
    if (argc != 2 && argc != 3)
    {
        printf("Usage: ./generate n [s]\n");
        return 1;
    }

    // Convert the inputted argument string into an int
    int n = atoi(argv[1]);

    // Influence the drand48 by using a seed, either with the inputted argument or based on time
    if (argc == 3)
    {
        srand48((long) atoi(argv[2]));
    }
    else
    {
        srand48((long) time(NULL));
    }

    // print out random numbers n many times.
    for (int i = 0; i < n; i++)
    {
        printf("%i\n", (int) (drand48() * LIMIT));
    }

    // success
    return 0;
}

helpers.c

/**
 * helpers.c
 *
 * Helper functions for Problem Set 3.
 */

#include <cs50.h>

#include "helpers.h"

/**
 * Returns true if value is in array of n values, else false.
 */
//Binary Search O(log n)
bool search(int value, int values[], int n)
{
    int start, end, mid;
    if(value <0)
    {
        return false;
    }
    else
    {
        start = 0;
        end = n;
        do
        {
            mid = ((start + end)/2);
            if (value == values[mid])
            {
                return true;
                break;
            }
            else if(value < values[mid])
            {
                end = mid-1;
            }
            else if(value > values[mid])
            {
                start = mid +1;
            }
            n = end - start;
        }
        while ( n >= 0 );
        return false;
    }
}

/**
 * Sorts array of n values.
 */

 //Counting Sort O(n)
void sort(int values[], int n)
{
    int MAX = 65536;
    int count[MAX];
    //Reset the array to 0 to avoid null values;
    for (int i=0; i<MAX; i++)
    {
         count[i] = 0;
    }

    //Increment the count array value at the index of the values array
    for (int i=0; i<n; i++)
    {
        count[values[i]]++;
    }

    //We can now fill the values array with the index value of the count array
    //and decrement the count array values until they are empty
    int index = 0;
    for (int i=0; i<MAX; i++)
    {
        while (count[i] > 0)
        {
            values[index] = i;
            index++;
            count[i]--;
        }
    }
}

helpers.h

/**
 * helpers.h
 *
 * Helper functions for Problem Set 3.
 */

#include <cs50.h>

/**
 * Returns true if value is in array of n values, else false.
 */
bool search(int value, int values[], int n);

/**
 * Sorts array of n values.
 */
void sort(int values[], int n);