1. Find the middle number between two numbers

Example: in an array we need to find the middle index position of the array

  1. mid = l + (r - l) / 2
  2. mid = (l + r) / 2
int[] arr = new int[10];
int l = 0, r = arr.length - 1;
int mid = (l + r) / 2;

// set mid = 5
Copy the code

1. Comparison of the two methods

Method one is the first method that comes to our mind when we learn and understand the problem. Method two is the simplification of method one, which is the most common and engraved method in our mind in mathematics and our daily programming. However, there is a fatal flaw in the programming of method 2: because the int type in the programming is bounded, when the l and R we want to calculate are very close to the boundary value, l + R may be greater than the maximum value of int, causing an exception.

Now, there are people who say, well, let’s think about changing int to long, that’s a good way to do it, and it works in most cases. But I think it’s a palliative. Can we go back to method one at this point and see if we can solve this problem? Mid = l + (r-l) >> 1; mid = l + (r-l) >> 1;

2. Application scenarios of the two methods

  1. Method 1 generally applies to all scenarios;
  2. Method two is the case where we can be sure that we don’t add two numbers out of bounds.

2. Implement the rounding of division by yourself

When computing division, the default is to round down, such as 11/2 = 5, but sometimes we may need to round up, such as 11/2 returning 6.

1. Code presentation

/** * implements an integer division operation *@paramA dividend *@paramDivisor b * * /
public static int ceilDiv(int a, int b) {
    / / method
    // return a / b + (a % b > 0 ? 0:1)

    / / method 2
    return (a + b - 1) / b;
    
}
Copy the code

2. Explanation of the two methods

Method one is easier to understand, if a/ B has no remainder, then there is no rounding problem; If a over b has a remainder, then we’re going to round up, and we’re going to round up by taking the quotient plus 1.

Method two and this is probably a little bit of a roundabout. Let’s give two examples that might make it easier to understand. Such as:

Case 1 8/5 => (8 + 5-1) /5 = 12/5 = 2 Case 2 6/2 => (6 + 2-1) /2 = 7/2 = 3

The formula for method two is a + (b – 1).

So let’s understand that b minus 1 is actually the largest remainder of b. We add the maximum remainder of the divider to the dividend, and then divide the divider according to the computer’s integer division method. ① If there is no remainder, then we add the maximum remainder, and it will still be thrown away. ② If the remainder is greater than or equal to 1, then we add a maximum remainder, and we get the quotient +1, which is equivalent to rounding up.

** Here we can see that the core idea of the two methods is completely the same: both carry out the quotient +1 operation when there is a remainder. ** Of course, this is also the basic idea of rounding up, otherwise there is no concept of rounding up. Ha ha ~

3. Attachment: achieve their own round

To round, we usually add +0.5 to the end of the result and use the system default round down

(11 / 2f) + 0.5 f = 5.5 + 0.5 = 6;
(10 / 4f) + 0.5 f = 2.25 + 0.5 = 2.75 = 2
Copy the code