Why does this recursive binary search impl overflows?

struct Solution {
    bad_number: i32,
}

impl Solution {

    //input 5 retruns 2;
    pub fn first_bad_version(&self, n: i32) -> i32 {
        Solution::bin_ser(self, n / 2, n)
    }

    fn bin_ser(&self, h: i32, n: i32) -> i32 {
        if !self.is_bad_version(h - 1) && self.is_bad_version(h) {
            h
        } else if self.is_bad_version(h) && self.is_bad_version(h - 1) {
            Solution::bin_ser(self, h / 2, h)
        } else
        {
            Solution::bin_ser(self, h + (n - h) / 2, n)
        }
    }
    
    fn is_bad_version(&self, v: i32) -> bool {
        if v >= self.bad_number {
            return false;
        }
        true
    }
}

fn main() {
    let solution = Solution {
        bad_number: 2,
    };
    
    println!("{}",solution.first_bad_version(5));
}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
    Finished dev [unoptimized + debuginfo] target(s) in 1.75s
     Running `target/debug/playground`

thread 'main' has overflowed its stack
fatal runtime error: stack overflow
timeout: the monitored command dumped core
/playground/tools/entrypoint.sh: line 11:     8 Aborted                 timeout --signal=KILL ${timeout} "$@"

If you take the last branch and n - h == 1 -- for example in your playground, when n == 5 and h == 4 -- then you call the same method recursively with the same numbers as (n - h) / 2 evaluates to 0.

Since you called it with the same numbers, it will do the same thing and recursively call itself until you smash the stack.

1 Like

I understand, thanks

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.