4
votes
Pset3 Binary Search problems
There was a question about this question on facebook, so instead of replying there, I thought I'd try to give some examples here, to supplement Cliff's amazing answer. It might be that none of this ...
- 834
4
votes
Accepted
Question about binary search. Please help!
Even or odd, it doesn't really matter. The point is that you are dividing the list approximately in half, give or take. If the split doesn't occur exactly at the middle (odd number of elements), it ...
- 68.4k
3
votes
Accepted
How do I set a pointer to access the left half of an array? [PSET 3 - Binary search]
For a binary search, you keep only one range, not two. That one could be specified by either a pointer to the start of the range and a length, or a left and right index limiting the range (the version ...
- 20.9k
3
votes
Accepted
Need help with recursive binary search
When you call a recursive function, you actually need to deal with the return value of that function. You are currently just calling BinarySearch(key, array, min, midpoint-1) for example and then ...
- 18.6k
2
votes
Accepted
Recursive find.c - not returning
regardless of the correctness of the algorithm, generally speaking, if you want a function to return the value of an expression, you may return the expression itself. for example:
return 16 + 26; // ...
- 17.7k
2
votes
Accepted
pset3 Binary search error message : Control may reach end of non-void function
To the compiler, it is possible that all of the if conditions could be false and none of the returns would ever execute. So, it's not happy. (Also, I believe this is a warning, but all warnings are ...
- 68.4k
2
votes
Accepted
Do While loop not executing for pset3
Right before bool sorted = false;, you have return true;. You give a return value before anything else happens, so your function does exactly that: it returns that value and stops executing any ...
- 1,412
2
votes
Accepted
how effective would it have been to use an array for the dictionary?
suppose we are to implement speller using an array instead of a hash-table or a trie.
a main problem that we have is that we don't know the number of words in the dictionary in advance (yes, we know ...
- 17.7k
2
votes
Accepted
find.c compiles but fails check50 - I believe binary search is to blame
The reason that the other questions aren't helping is that you've come up with a problem that appears to be unique. Take a look at the following code, particularly the test condition:
if (values[...
- 68.4k
2
votes
Accepted
return -1 does not end function execution
It does return, but you have to understand where it returns to. When a return executes, it returns control to the function that called it. In this case, since BinarySearch() recursively calls itself, ...
- 68.4k
2
votes
Accepted
Binary Search pset3
Q1: Remember this: COMPILERS ARE DUMB! While it may be logically impossible to not execute a return, compilers aren't capable of interpreting all of the complex logic possibilities to know. So, they ...
- 68.4k
2
votes
C: Pset 3: Binary Search - 'expected an exit code of 0, not 1' (not finding n)
Actually what you had written is not a binary search as in each move its not changing the size of array to half of original size.
By the way mistake in your code is in line no. 19 and 30 as you are ...
- 252
1
vote
Accepted
cs50x pset3 find - Need help with the counting sort
One problem I see with your sort function is that you've made a third array (sortedArray[]) and filled it with sorted numbers from values[], but then you didn't do anything else with it. Your function ...
- 117
1
vote
Accepted
C: Binary Search searches and finds but incorrect exit code
Appropriate while loop would be while (max >= min), looping as long as the search interval has elements.
If values[mid] > value, it means the value (if present) would be on the left, so set max ...
- 20.9k
1
vote
Accepted
Advice re: Binary search - various issues
Here is Zamyla's pseudocode for search
while (length of list > 0)
look at middle of list
if number found, return true
else if number higher, search left
else if number lower, ...
- 26
1
vote
Accepted
C: Pset 3: Binary Search - 'expected an exit code of 0, not 1' (not finding n)
When you write
int min;
int max;
you're creating two int variables, but their value is undefined, it's the value that happened to be at that place in memory when they were created.
You don't assign ...
- 20.9k
1
vote
Accepted
Recursive function problem - return value
Currently, if binarySearch does not score a direct hit (values[midpoint] == value), it does not return anything. In those cases, however, you should return the result of the recursive call, which you ...
- 20.9k
1
vote
Accepted
Pset3 recursive binary search function - check50 gives me four :( and I don't know why
Based on the comments in your code and without doing much analysis, I'd say that you have fallen victim to a very common error for new programmers.
A bool is either true or false. It can also be ...
- 68.4k
1
vote
Accepted
Segmentation fault in find.c
There are two problems - an infinite loop and a parameter that is out of range.
Infinite loop: In binarysearch(), when the target is not in the list, the recursive calls will eventually get to a ...
- 68.4k
1
vote
Accepted
Check50 is claiming that it's recieving an exit code of 0 rather than 1 (different scenario)
This code will never find anything unless value == midpoint. On each pass through the loop, it updates the min or the max, but it never updates midpoint. Since midpoint never changes, the loop will ...
- 68.4k
1
vote
Stuck in loop on Binary Search
Keep in mind that = is an assignment operator. It assigns right value to left value. Any subsequent changes to that right value won't have an effect on left value unless you assign it again.
Same ...
- 313
1
vote
Pset 3 - Binary Search - clang: error: linker command failed with exit code 1
The error message means the term "search" is not defined. Did you change the function name in helpers.c? It looks like you have "binarySearch" instead of "search".
- 1,415
1
vote
Accepted
check50 fails to compile helpers.c - throws implicit function declaration error
Header files act as a snippet informing programs that use it, "Okay. I've prepared these functions for you. You don't have to know how it works under the hood. It's not your business if I'm secretly ...
- 313
1
vote
Odd bug for Find
Your problem lies in these lines:
for (int i = 0; i < n; i++)
{
if (values[i] > values[i+1])
If there are n elements in array values[], what happens when i=n-1 and you try to ...
- 68.4k
1
vote
Accepted
Having trouble with pset3 helpers.c binary search
It's going into an infinite loop when the needle is the last number in the stack. If you were to print out the values for min, mid and max, you'd be surprised. I did so, along with a pass counter and ...
- 68.4k
1
vote
Accepted
Bug in my Pset3 Binary Search helpers.c
Take a look at the following three lines of code and tell me what's different?
if (value == values[middle])
else if (value > middle)
else if (value < middle)
Why is the first one ...
- 68.4k
1
vote
Accepted
What's wrong with my binary search code?
You're setting "low" and "high" to values[middle - 1]. That is the value stored in that array location, and NOT the index of the array. So, suppose you have this case:
values = {42, 43, 44}
looking ...
- 1,687
1
vote
Accepted
Find.c (Binary Search)
I tested your search code and it's working fine. Binary search is dependent on the list being a sorted list. If the list isn't sorted, the search may or may not work.
You should verify that your ...
- 68.4k
1
vote
Accepted
PSET3 - Recursive binary search always returning false
Perhaps you're looking in the wrong haystack. ;-) I ran your code and it works fine. I believe that it is more likely to be a problem with your sort routine. Have you verified that it is working ...
- 68.4k
1
vote
Accepted
Pset3 - Function returns both true and false in while loop
The sm() function recursively calls itself, but fails to recursively return the result. For a detailed discussion, check out Pset3 Binary Search problems
The break in this while loop forces the loop ...
- 68.4k
Only top scored, non community-wiki answers of a minimum length are eligible