Claudia Claudia - 1 month ago 11
C Question

Recursive Linear Search in C debug

Problem:1
In this code if I search a number which is not in array it should display

Value not found
but I don't know it's not displaying that message instead everytime it's showing
Found value in element -5
I don't have any clue why it's happening.

#include<stdio.h>
#define SIZE 100

size_t linearSearch(const int array[], int key, size_t size);

int main(void)
{

int a[SIZE];
size_t x;
int searchKey;
size_t element;


for(x=0; x<SIZE; ++x){
a[x] = 2*x;
}

for(x=0; x<SIZE; ++x){
if(x%10 == 0){
puts("");
}
printf("%5d", a[x]);
}

puts("\n\nEnter integer search key:");
scanf("%d", &searchKey);

// attempt to locate searchKey in array a
element = linearSearch(a, searchKey, SIZE);

// display results
if(element != -1){
printf("Found value in element %d", element);
}
else{
puts("Value not found");
}
}

size_t linearSearch(const int array[], int key, size_t size)
{
if(size<0){
return -1;
}
if(key == array[size-1]){
return size-1;
}
return linearSearch(array, key, size-1);

}


Problem:2

I can't understood how


size_t linearSearch(const int array[], int key, size_t size)


function working specially these line

if(key == array[size-1]){
return size-1;
return linearSearch(array, key, size-1);

Answer

As everyone said that you have a little mistake that is, you should write if(size==0) not if(size<0).

let me explain what's going on recursively in linearSearch() function

size_t linearSearch(const int array[], int key, size_t size)
{
    if(size == 0){
        return -1;
    }
    else
        if(key == array[size-1]){
            return size-1;
    }
    else{
        return linearSearch(array, key, size-1);
    }
}

Suppose you gave an input 198 as searchkey. When you calling linearSearch() function by the statement

element = linearSearch(a, searchKey, SIZE);

you are passing reference to array[], searchKey 198, and Size 100 as argument.

In linearSearch function first if statement if(size==0) checks if the size is equal to zero if not then else if statement runs.

in else if statement If(198 == array[100-1]) condition is checked. and we see 198 is present in array[99] so the else if condition is true thus linearSearch function return the 99 as result.

Now lets see what happend if you input 55 which is not in the array list. if(size==0) is not true so program will skip it and will go to the next statement. if(55 == array[100-1] will be checked as its not true then linearSearch(array, 55, 100-1) will be called. again if(55==array[99-1]) will be checked. at some point size will become 0. and the first if(size==0) statement will execute.