Chapter 1: Binary search

1 Code implementation

Public BoolEN binSearch(int[] numbers, int target){if(numbers == null) return false; Int low = 0; int high = numbers.length - 1; While (low <= high){//int mid = (end + start)>>>1; Int mid = (high-low)/2 + low; If (numbers[mid] == target){return true; } else(numbers[mid] > target){count [mid] = mid; } else{// continue with R[mid+1..high] low = mid+1; } } return false; }Copy the code

2. Pay attention to detail

(1) Integer overflow problem when using (low+high)/2

The problem occurs when low+high is greater than the maximum value of the expression’s result type. Thus, overflow and /2 will not produce the correct result. Low +((high-low)/2) does not have this problem

(2) int middle = start + (end – start) >> 1;

  • The right shift here can be replaced by a division by two, because there will be no overflow. But moving to the right is more efficient

  • This calculation method is actually on the basis of intuitive thinking made a transformation

  • The intuitive way to think about it is you divide by 2 and you take the middle,

  • So this is sort of like how do you get the middle value based on the starting value or the ending value

  • It’s kind of confusing to say, for example, if we start at 2 and end at 6, we can easily figure out that the median is 4. But the truth is this

  • Is a pointer to starting point zero. For the starting value, this 4 is the starting value plus 2. So this plus 2 is going to be the end value minus the start value and then dividing by 2.

  • Due to the way Java is rounded down, we cannot subtract the difference from the end value to get the middle value

(3) int middle = (end + start) >>> 1;

  • In this way, addition overflows, but the unsigned right shift guarantees correctness

  • You can’t get a negative number if you add 0 to the unsigned right

Three other

public static void main(String[] args) { int low = Integer.MAX_VALUE; int high = Integer.MAX_VALUE; System.out.println(low); //2147483647 System.out.println(high); //2147483647 System.out.println(low + high); //-2 System.out.println("---------"); System.out.println((low + high)/2); //-1 System.out.println((low + high)>>2); //-1 System.out.println((low + high)>>>2); //2147483647 System.out.println((high - low)/2 + low); //2147483647}Copy the code