Tuesday, 12 October 2021

Java integer overflow and binary search

The below is two solutions for Leet code 374

Solution one

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int high = n;
        int low = 1;
        
        while (low<=high) {
            int mid = (low+high)/2;
            
            if (guess(mid) == 0) {
                return mid;
            }
            
            if (guess(mid) >0) {
                low = mid +1;
            } else {
                high = mid -1;
            }
        
        }
       
        return 0;
            
    }
}

Solution two

public class Solution extends GuessGame {
    public int guessNumber(int n) {
        int high = n;
        int low = 1;
        
        while (low<=high) {
            int mid = low + (high-low)/2;
            
            if (guess(mid) == 0) {
                return mid;
            }
            
            if (guess(mid) >0) {
                low = mid +1;
            } else {
                high = mid -1;
            }
        
        }
       
        return 0;
            
    }
}

These two solutions are almost identical. However, the first solution will not pass all tests. So, what is going on? The only difference is how to calculate mid value.


//solution one
int mid = (low+high)/2;

//solution two
int mid = low + (high-low)/2;

For solution one, it will cause integer overflow for large inputs.

No comments:

Post a Comment