CS50 week3 find

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[])
{
    // make sure user enters at least one commend-line argument but not more than two
    if (argc != 2 && argc != 3)
    {
        printf("Usage: ./generate n [s]\n");
        return 1;
    }

    // convert commend-line argument string (argv[1]) into an integer
    int n = atoi(argv[1]);

    // "seed" drand48 calling srand48 with an argument if it was given by user, otherwise call drand48 without seeding it
    if (argc == 3)
    {
        srand48((long) atoi(argv[2]));
    }
    else
    {
        srand48((long) time(NULL));
    }

    // print pseudorandom integers within the given LIMIT
    for (int i = 0; i < n; i++)
    {
        printf("%i\n", (int) (drand48() * LIMIT));
    }

    // success
    return 0;
}

helpers.c

/**
 * CS50 pset3 find
 * helpers.c
 *
 * 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.
 */
bool search(int value, int values[], int n)
{
   //check if n is positive integer
   if (n<0)
   {
       return false;
   }
   else 
   {
       int left, mid, right;
       //assign indexes to the left and rignt points of the search
       left=0;
       right=n-1;
       
       //search for the value using "while loop" while left less than or equals to right
       while (left<=right)
   {
       mid=(left+right)/2;
       
       //check if the value of the mid point of the respective "half" of array equals the searched value
       if (value<values[mid]) 
       {
         right=mid-1;
       }
       else if (value>values[mid])
       {
         left=mid+1;
       }
       else if (value==values[mid])
       {
           return true;
           break;
       }
   }
   return false;
   }
}

/**
 * Sorts array of n values.
 */
void sort(int values[], int n)
{   
    // implement an O(n+k) sorting algorithm (count sort)
    //create a count array and store 0 value in each of them
   int count[65536] = {0};
    
    //take a count array to store value of 1 in the respective indices
    for(int i=0; i<n; i++)
        {
            count[values[i]]=count[values[i]]+1;
        }
    //iterate over count array to find elements with a value greater than 0 
    //and store the index of that element to the original array being sorted
    for(int i=0, j=0; i<65536; i++)
    {
        if(count[i]>0)
        {
            //use condition to check if count array element contains value of 1 (which means
            //that this particular value (the index of caount array) found in the values[] only ones)
            if(count[i]==1)
            {
                //store the index of count[] into element of sorted values[] in incrementing order
                values[j]=i;
                j++;
            }
            else
            {
                //use while loop for count array element which is greater than 1 to store values in sorted array values[]
                //(for those elements of values[] which found in the values[] more than ones)
                while(count[i]>0)
            {
                values[j]=i;
                count[i]=count[i]-1;
                j++;
            }
            }
        }   
    }
    
    return;
}

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

Makefile

#
# Makefile
# CS50
#

all: find generate

find: find.c helpers.c helpers.h
	clang -ggdb3 -O0 -std=c11 -Wall -Werror -o find find.c helpers.c -lcs50 -lm

generate: generate.c
	clang -ggdb3 -O0 -std=c11 -Wall -Werror -o generate generate.c

clean:
	rm -f *.o a.out core find generate