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 ...
Sam Gerber's user avatar
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 ...
Cliff B's user avatar
  • 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 ...
Blauelf's user avatar
  • 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 ...
curiouskiwi's user avatar
  • 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; // ...
kzidane's user avatar
  • 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 ...
Cliff B's user avatar
  • 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 ...
Peter's user avatar
  • 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 ...
kzidane's user avatar
  • 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[...
Cliff B's user avatar
  • 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, ...
Cliff B's user avatar
  • 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 ...
Cliff B's user avatar
  • 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 ...
Rahul's user avatar
  • 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 ...
ArtemPetrov's user avatar
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 ...
Blauelf's user avatar
  • 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, ...
Yuu's user avatar
  • 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 ...
Blauelf's user avatar
  • 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 ...
Blauelf's user avatar
  • 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 ...
Cliff B's user avatar
  • 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 ...
Cliff B's user avatar
  • 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 ...
Cliff B's user avatar
  • 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 ...
aquablitz11's user avatar
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".
ronga's user avatar
  • 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 ...
aquablitz11's user avatar
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 ...
Cliff B's user avatar
  • 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 ...
Cliff B's user avatar
  • 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 ...
Cliff B's user avatar
  • 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 ...
Irene's user avatar
  • 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 ...
Cliff B's user avatar
  • 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 ...
Cliff B's user avatar
  • 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 ...
Cliff B's user avatar
  • 68.4k

Only top scored, non community-wiki answers of a minimum length are eligible