What am I doing wrong here? The prototypes aren't changeable. I need to write both of the functions and this is what I wrote. They work at 90% of the times. The iterative way got an issue when i'm trying to search for the middle element.
And the recursive way got some issue but I don't really know what's wrong. Sometimes it finds the element and other times not.
One more thing I cannot change it's that I must avoid checking inside of the function whether array[middle] == key. The teacher wants us to do this check only when I exit the loop, and he wants the loop to only check if should I go right or left.
int *BinarySearchIter(const int SortedArray[], int key, size_t length)
{
/* variables that will set the boundries of the searched area */
int left_index = 0, right_index = 0, middle = 0;
int *result = NULL;
assert(SortedArray);
assert(length);
left_index = 0; /* first elemenet in the array */
right_index = length - 1; /* last elemenet in the array */
/* while only one elemenet is left in the searched area */
while (left_index <= right_index)
{
/* split it to half */
middle = (left_index + right_index) / 2;
/* if key greater, ignore left half, search only in right half */
if (SortedArray[middle] < key)
{
left_index = middle + 1;
}
/* if key smaller, ignore right half, search only in left half */
else
{
right_index = middle - 1;
}
}
/* if we reach here, then element is the key or was not found */
result = (int *)SortedArray + middle;
return (key == *result ? result : NULL);
}
/******************************************************************************/
int *BinarySearchRec(const int SortedArray[], int key, size_t length)
{
int left_index = 0; /* first elemenet of the array */
int right_index = length - 1; /* last elemenet in the array */
int middle = 0, isBigger = 0;
if (1 == length)
{
return (key == *SortedArray ? (int *)SortedArray : NULL);
}
middle = (left_index + right_index) / 2;
isBigger = (key > SortedArray[middle]);
return (BinarySearchRec(SortedArray+(middle + 1)*isBigger, key, isBigger * (length - length /2 ) + !isBigger*(length/2)));
}
/******************************************************************************/
I was trying to run the following test;
const int sorted_arr[] = { 2, 4, 8, 10, 12};
size_t arr_length = sizeof(sorted_arr) / sizeof(sorted_arr[0]), i = 0;
int key_to_find = 0;
int *iterative_res = NULL;
int *recursive_res = NULL;
for (i = 0; i < arr_length; ++i)
{
key_to_find = sorted_arr[i];
iterative_res = BinarySearchIter(sorted_arr, key_to_find, arr_length);
recursive_res = BinarySearchRec(sorted_arr, key_to_find, arr_length);
Print if any errors (nulls or key doesn't match any of the results)
}
And this is the output of the test:
ERRORS:
Needs to find: 8
But found:
Iterative: NULL (failure)
Recursive: NULL (failure)
Needs to find: 12
But found:
Iterative: 12 (success)
Recursive: NULL (failure)
Let's think what your code is doing. You have an array consists 5 elements and let's say you are searching for 8.
2 4 8 10 12
^
In the first iteration the values are like this:
left_index = 0, right_index = 4, middle_index = 2
In the if statement the program checks for (SortedArray[middle_index] < key) and that is wrong because 8 is not bigger than 8. So it executes the else statement. The mistake is here.
In the else statement you are discarding the middle element. But in this case middle element is the key that you are looking for.
So first thing that you need to change just like @Eric Postpischil said is changing your else statement to this:
else {
right_index = middle;
}
Let's continue with second iteration:
2 4 8
^
left_index = 0, right_index = 2, middle_index = 1
After the second iteration, third iteration is only going to consist 1 element.
8
left_index = 2, right_index = 2, middle_index = 2
At this point the program stucks in the infinite loop because it always executes the else statement. Left and right indexes always stay same.
So the second change that you need to do is changing your while condition to this:
while (left_index < right_index)
At this point when the left index and right index are equal, the loop will break. Than the last thing that you need to do is updating your middle index again. Or you can use left_index or right_index (which one is doesn't matter they are equal).
At the end, your function should look like this:
const int *BinarySearchIter(const int SortedArray[], int key, size_t length) {
int left_index = 0, right_index = length - 1;
while (left_index < right_index) {
int middle = (left_index + right_index) / 2;
if (SortedArray[middle] < key) {
left_index = middle + 1;
} else {
right_index = middle;
}
}
return SortedArray[right_index] == key ? SortedArray + right_index : NULL;
}
Only thing you need to change is this:
return BinarySearchRec(SortedArray+(middle + 1)*isBigger, key, (length / 2) + !isBigger * (length % 2));
The reasons are same as iterative function. You need to include the middle element. For lower part of the array, the array length needs to be equal to ceil(length / 2), and for upper part of the array, it needs to be equal to floor(length / 2).
You can also do this:
const int *BinarySearchRec(const int SortedArray[], int key, size_t length) {
if (1 == length) return (key == *SortedArray ? SortedArray : NULL);
int middle = (length + 1) / 2;
if (key >= SortedArray[middle]) return BinarySearchRec(SortedArray + middle, key, length / 2);
else return BinarySearchRec(SortedArray, key, middle);
}