Here's the question you clicked on:

55 members online
  • 0 replying
  • 0 viewing

UnkleRhaukus

  • 2 years ago

pset3/find, i need some help

  • This Question is Closed
  1. UnkleRhaukus
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    ``` /** * helpers.c * * Computer Science 50 * Problem Set 3 * * Helper functions for Problem Set 3. * * search 1. Linear search 2. Binary search * * sort 1. Selection sort */ #include <cs50.h> // computer science 50 library #include <stdio.h> // standard input-output library #include <math.h> // mathematics library #include "helpers.h" // helpers header file /** * Returns true if value is in array of n values, else false. */ bool search(int value, int values[], int n) { // Searching algorithm /** 1. Linear Search, O(n) **/ /* // Compare each element in values with value for (int i = 0; i < n; i++) { if (values[i]== value) return true; // value found } return false; // value not found } */ // sort the values smallest to largest sort(values, n); while (n > 0) { /** 2. Binary Search, O(lb n) **/ printf("\nvalue = %d\t\tvalues = [", value); // value for (int i = 0; i < n; i++) // values[] printf("%d, ", values[i]); printf("\b\b]\n"); // printf("n = %d, ", n); // n int mip = n/2; int mid = values[mip]; // printf("mip = %d, ", mip); // mip printf("middle = %d" , mid); // mid int new_values[mip]; if (value == mid) return true; // value found else if (value < mid) { printf("\tValue is less than middle\n"); for (int i = 0; i < mip+1; i++) // new values[] new_values[i] = values[i]; search(value, new_values, mip); } else if (value > mid) { printf("\tValue is greater than middle\n"); for (int i = 0; i < mip; i++) // new values[] new_values[i] = values[mip+i+1]; search(value, new_values, mip); } return false; }; return true; } /** * Sorts array of n values. */ void sort(int values[], int n) { // Sorting algorithm /** 1. Selection sort, O(n^2) **/ for (int i = 0; i < n; i++) { int smallest = values[i]; // set smallest value int smallest_location = i; // set smallest location for (int j = i + 1; j < n; j++) // compare with other values { if (smallest > values[j]) // if there is a smaller number { smallest = values[j]; // change value smallest_location = j; // change location } } // put the beginning of the list where the smallest number was values[smallest_location] = values[i]; // swap smallest location // place it in the begining of the list values[i] = smallest; // swap smallest value // display /* printf("%d ", values[i]); // print values [hidden] */ } return; } ```

  2. UnkleRhaukus
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    i have some serious bugs in the binary search algorithm ``` jharvard@appliance (~/Dropbox/pset3/find): ./generate 9 2 | ./find 19 haystack[0] = haystack[1] = haystack[2] = haystack[3] = haystack[4] = haystack[5] = haystack[6] = haystack[7] = haystack[8] = haystack[9] = value = 19 values = [1, 4, 5, 8, 10, 15, 17, 18, 19] middle = 10 Value is greater than middle value = 19 values = [15, 17, 18, 19] middle = 18 Value is greater than middle value = 19 values = [19, 1204366368] middle = 1204366368 Value is less than middle value = 19 values = [19] middle = 19 Didn't find needle in haystack. ```

  3. UnkleRhaukus
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    ``` jharvard@appliance (~/Dropbox/pset3/find): ./generate 9 2 | ./find 1 haystack[0] = haystack[1] = haystack[2] = haystack[3] = haystack[4] = haystack[5] = haystack[6] = haystack[7] = haystack[8] = haystack[9] = value = 1 values = [1, 4, 5, 8, 10, 15, 17, 18, 19] middle = 10 Value is less than middle value = 1 values = [1, 4, 5, 8] middle = 5 Value is less than middle value = 1 values = [1, 4] middle = 4 Value is less than middle value = 1 values = [1] middle = 1 Didn't find needle in haystack. ``` with this input it almost works, but i still can't get the right `return` value

  4. wio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Consider a simple array where indices are the values: 0 1 2 3 4 5 We start with a length of 6. Half that to get 3. 0 1 2 <3> 4 5 If it is equal, we can return 3. If it is less, we simply change our length to 3 new values: 0 1 2 If is it greater, we shift out array pointer over by 3+1 = 4 new values: 4 5 _ _ _ _ We change our length to 6 - (3-1) = 2 4 5 Basic algorithm ``` bool search(int value, int values[], int n) { if (n < 1) { return false; } int mid = n/2; if (value < values[mid]) { return search(value, values, mid); } else if (value > values[mid]) { return search(value, values - (mid+1), n - (mid+1)); } return true; } ```

  5. UnkleRhaukus
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    @wio you mean `We change our length to 6 - (3+1) = 2` right? also, doesn't minusing `(mid+1)` from `values` in the `else if` statement, only work because of the choice of array? I can't figure out how to run your code for some reason

  6. wio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    Actually it should add it to values, not subtract it.

  7. wio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    adding will return an array but it shifts what would be considered the 0 index by `(mid+1)`.

  8. wio
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 2

    so `values+(mid+1)`

  9. UnkleRhaukus
    • 2 years ago
    Best Response
    You've already chosen the best response.
    Medals 1

    Thanks wio, i have managed to get my script to work now using the help of you script. ``` jharvard@appliance (~/Dropbox/pset3/find): ./generate 32 0 | ./find 52711 haystack[0] = haystack[1] = haystack[2] = haystack[3] = haystack[4] = haystack[5] = haystack[6] = haystack[7] = haystack[8] = haystack[9] = haystack[10] = haystack[11] = haystack[12] = haystack[13] = haystack[14] = haystack[15] = haystack[16] = haystack[17] = haystack[18] = haystack[19] = haystack[20] = haystack[21] = haystack[22] = haystack[23] = haystack[24] = haystack[25] = haystack[26] = haystack[27] = haystack[28] = haystack[29] = haystack[30] = haystack[31] = haystack[32] = value = 52711 values = [124, 1946, 2132, 3958, 7931, 7977, 8987, 9158, 9562, 10232, 16882, 17293, 17767, 18547, 22714, 22764, 23807, 25282, 29283, 31949, 37962, 39017, 43491, 49715, 50377, 52711, 55199, 55211, 56401, 57670, 59880, 63790] middle = 23807 Value is greater than middle value = 52711 values = [0, 25282, 29283, 31949, 37962, 39017, 43491, 49715, 50377, 52711, 55199, 55211, 56401, 57670, 59880, 63790] middle = 50377 Value is greater than middle value = 52711 values = [52711, 55199, 55211, 56401, 57670, 59880, 63790, 1204366368] middle = 57670 Value is less than middle value = 52711 values = [52711, 55199, 55211, 56401] middle = 55211 Value is less than middle value = 52711 values = [52711, 55199] middle = 55199 Value is less than middle value = 52711 values = [52711] middle = 52711 Value is equal to middle! Found needle in haystack! ```

  10. Not the answer you are looking for?
    Search for more explanations.

    • Attachments:

Ask your own question

Sign Up
Find more explanations on OpenStudy
Privacy Policy