C++

Forum

 
Segmentation fault in recursive binary search

colstj46 (3)
Hello

For one of my labs I am to create a quarter search(similar to binary search but split into quarters instead of halves). This is called recursively and we must use pointers. This is the code I have so far But i receive a segmentation fault. I'm pretty sure this is during the recursive call area. Can anyone point out where my code goes bad?


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
 
bool quadSearch(int *arr,int value,int length){
        int half = length/2;
        int quarter = half/2;
        int threeFourths = half+quarter;
        if(value == *(arr+quarter)){
                return true;
        }
        if(value == *(arr+half)){
                return true;
        }
        if(value == *(arr+threeFourths)){
                return true;
        }
        if(value < *(arr+quarter)){
                int * ptrTemp = new int[quarter];
                for(int i=0; i<quarter; i++){
                        *(ptrTemp+i) = *(arr+i);
                }
                quadSearch(ptrTemp,value,quarter);
        }
        else if(value > *(arr+threeFourths)){
                int * ptrTemp = new int[quarter];
                for(int i=0; i<quarter; i++){
                       *(ptrTemp+i) = *(arr+(threeFourths+i));
                }
                quadSearch(ptrTemp,value,quarter);
        }
        else if(value > *(arr+half) && value < *(arr+threeFourths)){
                int *ptrTemp = new int[quarter];
                for(int i=0; i<quarter; i++){
                        *(ptrTemp+i) = *(arr+(half+i));
                }
                quadSearch(ptrTemp,value,quarter);
        }
        else{
                int *ptrTemp = new int[quarter];
                for(int i=0; i<quarter; i++){
                        *(ptrTemp+i) = *(arr+(quarter+i));
                }
                quadSearch(ptrTemp,value,quarter);
        }
        return false;
}

Last edited on
Peter87 (11234)
You should return the return value of the calls to quadSearch.

You also need to handle the case when length == 0?

colstj46 (3)
A little confused with what you mean return the return values? And yes I will take care of the length == 0 case
cire (8284)
A little confused with what you mean return the return values?


Every time you call quadSearch recursively you discard the return value and return false.
colstj46 (3)
Ok so this is my new code it compiles but never returns true or false just 0

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 
bool quadSearch(int *arr,int value,int length){
        int half = length/2;
        int quarter = half/2;
        int threeFourths = half+quarter;
        if(length == 0){
                return false;
        }
        if(value == *(arr+quarter)){
                return true;
        }
        if(value == *(arr+half)){
                return true;
        }
        if(value == *(arr+threeFourths)){
                return true;
        }
        if(value < *(arr+quarter)){
                int * ptrTemp = new int[quarter];
                for(int i=0; i<quarter; i++){
                        *(ptrTemp+i) = *(arr+i);
                }
                quadSearch(ptrTemp,value,quarter);
        }
        else if(value > *(arr+threeFourths)){
                int * ptrTemp = new int[quarter];
                for(int i=0; i<quarter; i++){
                       *(ptrTemp+i) = *(arr+(threeFourths+i));
                }
                quadSearch(ptrTemp,value,quarter);
        }
        else if(value > *(arr+half) && value < *(arr+threeFourths)){
                int *ptrTemp = new int[quarter];
                for(int i=0; i<quarter; i++){
                        *(ptrTemp+i) = *(arr+(half+i));
                }
                quadSearch(ptrTemp,value,quarter);
        }
        else{
                int *ptrTemp = new int[quarter];
                for(int i=0; i<quarter; i++){
                        *(ptrTemp+i) = *(arr+(quarter+i));
                }
               quadSearch(ptrTemp,value,quarter);
        }
}


any other tips how to make this work?
Last edited on
cire (8284)
Yes. Pay attention to what your compiler is tellling you about that function not always returning a value.

You're still discarding the return values any time you call quadSearch recursively, but instead of returning false you're evoking undefined behavior by returning nothing from a function that requires a return value.

return quadSearch(ptrTemp, value, quarter) ;
Topic archived. No new replies allowed.