Segmentation fault in recursive binary search

Oct 4, 2012 at 6:39pm
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 Oct 5, 2012 at 12:22am
Oct 4, 2012 at 6:52pm
Peter87 (11251)
You should return the return value of the calls to quadSearch.

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

Oct 4, 2012 at 7:02pm
colstj46 (3)
A little confused with what you mean return the return values? And yes I will take care of the length == 0 case
Oct 4, 2012 at 8:35pm
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.
Oct 5, 2012 at 12:19am
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 Oct 5, 2012 at 12:22am
Oct 5, 2012 at 6:47am
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.