0

Trying out a recursive binary search algorithm, it returns the correct target that I pass it but at the wrong index.

The index seems to always be the center index of the high and low values.

I added some printf's in the binarySearch if statements, and it seams it never calls itself recursively, always returns with the mid value.

Even if you change the target to a value not held within the array, it returns with index 5, and the correct target value.

int main(void)
{
    int const numbers[10] = {1,3,4,7,13, 14, 17, 18, 20, 23};
    int const target = 20;
    int result = 0;
    result = binarySearch(&numbers, 0, 10, target);
    if (result != -1)
    {
        printf("Element is found in array in index: %d, and holds value: %d\n", result + 1, numbers[result]);
    }
    else
    {
        printf("Element is not found in array\n");
    }
}

int binarySearch(int* arr, int low, int high, int x)
{
    if (high >= low)
    {
        int mid = low + (high - low) / 2;
        if (arr[mid] = x)
        {
            printf("mid\n");
            return mid;
        }
        else if (arr[mid] > x)
        {
            printf("high\n");
            return binarySearch(arr, low, mid - 1, x);
        }
        else if (arr[mid] < x)
        {
            printf("low\n");
            return binarySearch(arr, mid + 1 , high, x);
        }   
    }
    else
    {
        return -1;
    }
}

OUTPUT

Element is found in array in index: 5, and holds a value of: 20

Thoughts?

8
  • 3
    Did your compiler not whine about the if (arr[mid] = x) ? Did you mean == ? Commented Mar 15, 2020 at 18:21
  • compiling on server of Linux that my college provides, editing with Visual Studio 2019. didn't get any warnings but doing this solved my problem. Do you have a greater understanding why this would solve? (still new to C, and trying to be proficient in it) Commented Mar 15, 2020 at 18:44
  • 1
    As far as C is concerned, an assignment is an expression, whose value is the result of the assignment. So in if (arr[mid] = x), x is assigned to arr[mid], the result of the expression is the new value of arr[mid], ie 20 in this case, which is true as far as C is concerned. With ==, on the other hand, the expression returns 1 if the values on either side are equal. It's a standard gotcha in C. FWIW, doing a binary chop by recursion is a little exotic -- a loop will do the job. Commented Mar 15, 2020 at 19:03
  • 1
    Also: I think the initial call of binarySearch() should be 0, 9 not 1, 10 -- C arrays are 0 origin. You need to think carefully about what low and high refer to in binarySearch(). Commented Mar 15, 2020 at 19:04
  • 2
    Up to a point... sizeof(numbers) will give you the size of the array in bytes, in this case, probably 40. sizeof(numbers)/sizeof(numbers[0]) will give you the size of the array in elements, in this case 10. Noting that that's the size allocated, not the number of elements in your static initialisation { 1, 3, ... }. I'd change the binarySearch() to take const int* arrparameter -- which would then be consistent const numbers[] argument. Commented Mar 16, 2020 at 0:12

1 Answer 1

1

Simple mistake

As far as C is concernced arr[mid] = x is an assignment, not a comparison.

Since x is does not return to a 0, the if statement gets cleared and returns the wrong index, but the correct value. If we change the target to 0, the if statement returns false, and it doesn't return the mid index.

We need to change arr[mid] = x to arr[mid] == x to change it from a assignment to a comparison.

Sign up to request clarification or add additional context in comments.

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.