I was playing around with code for a binary search and insert.

Given an array of sorted integers, it should find the index of the target number. If it does not exist, then it should return the index of where it would be if inserted.

I found that the way I compute the mid causes my code to work differently.

I'm wondering if there is some difference between mid = (low high) / 2 and mid = low (high - low) / 2.

An input example: array [1,3,5,6] and a target value is 2.

    public static int searchInsert(int[] nums, int target) {
        int high = nums.length - 1;
        int low = 0;
        int mid = low   (high - low) / 2; // diff if use: (low   high) / 2
        
        for( ; low <= high ; ) {
            if(nums[mid] > target) {
                high = mid - 1;
            } else if(nums[mid] < target) {
                low = mid   1;
            } else {
                return mid;
            }
            mid = low   (high - low) / 2;  // diff if use: (low   high) / 2

            System.out.println(low   (high - low) / 2   ": "   high   " "   low);
            System.out.println(mid   " "   high   " "   low);
        }
        return mid;
    }

CodePudding user response：

The difference (with your example of numbers) is:

In one point (last loop iteration) you have low = 1 and high = 0.

In this case the formula (low high) / 2 comes out to (1 0) / 2, this is 1 / 2 and this evaluates to 0 (integer arithmetic).

But the formula low (high - low) / 2 comes out to 1 (0 - 1) / 2, this is 1 (-1 / 2) and further 1 0 because -1 / 2 is also 0 in integer arithmetic.

If you would have floating point steps it would boil down to (int) (1.0 / 2.0) vs. (int) 1.0 (int)(-1.0 / 2.0)