Integer Overflow in Java

While coding we may face some integer overflow cases for large inputs. Today I am going to discuss about two such scenarios which I have faced during problem solving.

Binary Search

Say you are given a sorted integer array and you are asked to find a particular element in that array. Since the array is sorted we can apply binary search algorithm to find the target element in O(logN) time; here N is the size of the input array.

The basic idea of binary search is each time we divide the array in half, find the mid index and compare the target element with the middle element. If the target element is greater than the middle element in that case we need to search only the right part of the array starting from the next index of the mid index. If the target element is less than the middle element then we need to search the left part of the array which ends before the mid index.

So the question is how we are going to find the mid index. It’s very simple; we need to maintain two pointers: start and end; start pointer is initialized with 0 and end pointer is initialized with N-1(N is the size of the array). So the formula we are going to use to find the mid index is:

mid = (start + end)/2.

At first glance this formula might seem innocent, but if we closely look at this formula we can see at first part it adds two integer numbers. Since we are adding two integer numbers there is a possibility of integer overflow if these two numbers are very…