A simple interview question: 90% of programmers can’t write this algorithm exactly right…

Some time ago, I saw statistics on the forum that 90% of programmers cannot write simple dichotomy correctly. Isn’t dichotomy easy? Isn’t that sensational?

Actually, dichotomy is really not that simple, especially the various variations of dichotomy. The simplest dichotomy is to find a key from a sorted array. The following procedure.

Static int binarySerach(int[] array, int key) {int left = 0; int right = array.length - 1; // This must be <=while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] == key) {
            return mid;
        }
        else if (array[mid] < key) {
            left = mid + 1;
        }
        else{ right = mid - 1; }}return- 1; }Copy the code

This procedure, believe that as long as is a qualified programmer should be able to write. Note that every time you move the left and right Pointers, you need to add +1 or -1 to mid to prevent an infinite loop and the program will run correctly.

But would you write if the conditions were slightly different? For example, the data in an array may be duplicated, requiring that the minimum (or maximum) subscript of the matched data be returned; Further, you need to find the index of the first element in the array greater than key (that is, the smallest element greater than key), and so on. These changes, though small, need to be implemented with greater care. The implementations of these binary retrieval variants are listed below.

1. Find the first element that is equal to key

Static int findFirstEqual(int[] array, int key) {int left = 0; int right = array.length - 1; // This must be <=while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid - 1;
        }
        else{ left = mid + 1; }}if (left < array.length && array[left] == key) {
        return left;
    }
    
    return- 1; }Copy the code

2. Find the last element equal to key

Static int findLastEqual(int[] array, int key) {int left = 0; int right = array.length - 1; // This must be <=while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] <= key) {
            left = mid + 1;
        }
        else{ right = mid - 1; }}if (right >= 0 && array[right] == key) {
        return right;
    }

    return- 1; }Copy the code

Find the first element equal to or greater than Key

Static int findFirstEqualLarger(int[] array, int key) {int left = 0; int right = array.length - 1; // This must be <=while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid - 1;
        }
        else{ left = mid + 1; }}return left;
}
Copy the code

Find the first element greater than key

Static int findFirstLarger(int[] array, int key) {int left = 0; int right = array.length - 1; // This must be <=while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] > key) {
            right = mid - 1;
        }
        else{ left = mid + 1; }}return left;
}
Copy the code

5. Find the last element equal to or less than key

Static int findLastEqualSmaller(int[] array, int key) {int left = 0; int right = array.length - 1; // This must be <=while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] > key) {
            right = mid - 1;
        }
        else{ left = mid + 1; }}return right;
}
Copy the code

Find the last element that is less than key

Static int findLastSmaller(int[] array, int key) {int left = 0; static int findLastSmaller(int[] array, int key) {int left = 0; int right = array.length - 1; // This must be <=while (left <= right) {
        int mid = (left + right) / 2;
        if (array[mid] >= key) {
            right = mid - 1;
        }
        else{ left = mid + 1; }}return right;
}
Copy the code

Next, you can test these four variants.

Most of the time, the application of binary search is not directly to find and key equal elements, but the use of the above mentioned binary search variations, master these variations, when you use binary search again when the search will feel more handy.