20
This is an example of a recursive call. Even though it is calling itself correctly, it is missing the code necessary to recursively return the result. As it is written above, it will execute the recursive call to itself, but when it does find a number, it will return true on the first step back through the recursion. However, at the second step and ...
6
To spot what's wrong with your algorithm, given the following sorted array
{1, 2, 3}
try with a pen and a paper finding these values
value = 1
value = 2
value = 3
value = 4
And try to figure out why your algorithm returns false every time.
The algorithm is actually way simpler than that, but let's talk about recursion a little bit first.
A recursive ...
5
There are two basic ways for implementing a binary search algorithm.
using recursion.
using loops.
Given values, a global int array that we're searching for value in. min, the minimum index, and max, the maximum index in the array/sub-array,
The Pseudocode for the Recursion Way Might Be
bool search (int min, int max, int value)
{
// the base case
...
4
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 makes sense, but it's how I wrap my mind around it. Feel free to correct as necessary.
Let's work off the simplest case, an array of {1, 2, 3}.
If we are ...
4
Common problem. The compiler looks at all the possible paths through the code and checks to see that there is going to be a guaranteed, unconditional return to satisfy the need for a return value. But, compilers are dumb. They don't recognize that you can create a fully conditional path that must hit a return.
In your case, the fix is simple. The final else ...
3
I inserted your search routine into my code and found an additional clue. When the needle is either the smallest or the largest number in the sorted list, it would fail. This should be recognized as a conspicuous clue.
So, you need to look at your code to see what happens when you're checking the ends of the list, either the small end or the large end. You ...
3
One of the skills that are indirectly taught in this class, as well as being one of the most important skills you must learn as a programmer is how to debug a program. You will run into seg faults frequently as a programmer, so you really need to learn how to isolate them yourself!
There are a number of techniques you can use. You could step through the ...
3
I don't want to sound cruel here, but your sort routine has serious problems. It is incomplete, it has code that appears to serve no purpose ( an if statement with no code to process if true), and doesn't compare any two elements in the list to sort (or at least not the two intended elements).
Your biggest problem (in my opinion) is that you are comparing, ...
3
You have declared an array called values.
When you say 'values[middle]', it refers to the middle element of array. On the other hand, 'values' refers to the address of the beginning of that array. You are actually comparing address of array with the one of the element of the same array.
I assume that you wanted to compare 'values[middle]' to the number you ...
3
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 throwing away whatever value it returns.
Be sure to return BinarySearch(...) whenever you call it.
Also, look again at your int midpoint value. If, for example, ...
3
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 with less pointers, probably leading to safer code).
Please note that in dividing the array in half, the two halves do not necessarily have to be of equal ...
3
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 can be either the element just before or after the midpoint (even number of elements). Eventually, it will come down to either two elements or 1 elements, ...
2
The main moto of the course is to increase your skills. If you think you have made a wrong implementation of any standard algorithm or feel a bit confusing in any topic, so you are free to search for it on Internet and in Reference books. If you have any doubts, then use the SE community or facebook page to clear them. Of-course that won't be against the ...
2
The code could exhibit a type of behaviour called an infinite loop. This means it never reaches an expected state where the loop would end, and so continues to run forever. Tip: To halt a program which has entered an infinite loop, press Ctrl+C.
The cause of the error is that the mid variable is not being recalculated. Note two lines of code which move the ...
2
Make a function declared as bool binsearch(int array[], int start, int end, int ele), with start being the starting index and end being the last index(exclusive), and ele is the element to be search in the array.
Initially call the function as binsearch(array, 0, len, ele), where len is the length of array. Now depending upon the value at mid element, the ...
2
You have a naming conflict with the previously defined function bsearch() in stdlib. Try changing the name of your bsearch() function to something like binsearch() and recompile.
If this answers your question, please click the check mark to accept this and remove the question from the unanswered pool. Let's keep up on forum maintenance. ;-)
2
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; // returns 42
similarly, if you want a function to return the value returned by a call to another function, you return that call. for example, to return the value ...
2
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 treated as errors due to a compiler flag.)
Simple fix. Uncomment the last return and change it to false, not true. You want it false because if the code ever ...
2
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 further code.
2
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 the number of words in the given dictionary per the specs, but our program should allow loading custom dictionaries).
as a result, we would have to ...
2
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[middle] > value)
{
first = middle + 1;
}
If the test condition is true, that means that the target is in the lower half of the list, but the ...
2
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, it returns to the previous execution of BinarySearch() that called the current recursion. It will not go directly back to main or the code that originally ...
2
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 don't try, beyond the most basic checks. So, the compiler looks for a structural way to complete execution of the function without executing a return, and it ...
2
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 writing
min = 0;
max = n - 1;
(values[mid])-1 which is wrong, it should be mid - 1 (line 19)
(values[mid])+1 which is wrong, it should be mid - 1 (line 30)
1
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 calling other functions just to make my jobs easier."
You shouldn't define binarysearch() prototype in helpers.h, because it's not what you want to present to ...
1
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 look at values[i+1]? What is i+1? Is it a legal value for an array element?
This causes an element to be sorted out the end of the array and a 0 to be ...
1
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 here's a sample for 40,41,42.
min=startpoint, mid= midpoint, max=endpoint
Count is the # of the current pass through the loop.
Count: 0, Min: 0, mid: 1, max: ...
1
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 different from the last two? Are you really checking to see if value is greater or less than the value of the array's index rather than an array element's ...
1
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 for 42
So:
low = 0; n = 3;
while loop starts, low < high
middle = 1 ((3+0)/2)
So we go to the last else if:
So, now you set "high" to be 42. Which ...
1
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 sort is working correctly. Use the same data that you are using for your search tests. Also, temporarily add a routine at the very end of your sort routine to ...
Only top voted, non community-wiki answers of a minimum length are eligible