Question

pset3/find, i need some help

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

Answer 2

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.
```

Answer 3

```
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

Answer 4

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

Answer 5

@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

Answer 6

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

Answer 7

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

Answer 8

so `values+(mid+1)`

Answer 9

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!

```