Preface science

The first binary search paper was published in 1946, while the first bug-free binary search method appeared in 1962, a period of 16 years.

In 2019, can you write a bug-free dichotomy search during an interview?

define

Dsmt4 search (binary search) is a search algorithm that looks for a specific element in an ordered array.

The search process starts with the middle element of the array, and ends if the middle element is exactly the element being searched.

If a particular element is greater than or less than the middle element, it looks in the half of the array that is greater than or less than the middle element, and compares from the middle element as it began.

If the array is empty at any step, it cannot be found.

This search algorithm reduces the search area by half with each comparison.

Binary search code

Following the above definition, let’s try to write binary search code.

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            mid = (min + max) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                returnmid; }}return -1;
    }
Copy the code

Now, is there a problem with this code? Which piece of code is buggy?

Think about it for a minute and check back later.

In the case of the above code, the problem is at line 6:

mid = (min + max) / 2;
Copy the code

This code overflows when min and Max are large, resulting in an array access error.

Although this error is now lightly pointed out, it was a mistake that existed for several years at the time.

So how can we improve it? The general way to do this is to change addition to subtraction.

public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // Prevent overflow
            mid =  min + (max - min) / 2;
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                returnmid; }}return -1;
    }
Copy the code

There is also a higher case notation, which is the official binary search implementation: use bitwise operations.

 public static int binary(int[] arr, int data) {
        int min = 0;
        int max = arr.length - 1;
        int mid;
        while (min <= max) {
            // Unsigned bit operators have lower precedence and are bracketed first
            mid =  min + ((max - min) >>> 1);
            if (arr[mid] > data) {
                max = mid - 1;
            } else if (arr[mid] < data) {
                min = mid + 1;
            } else {
                returnmid; }}return -1;
    }
Copy the code

Hopefully, today’s article will help readers write code by hand during the interview. After all, for many small companies, binary search will appear on their pen-based tests.