将它印入骨髓：二分查找及其变种算法

这两天阿清在想程序员的基础该如何评价？我认为手边的代码是非常重要的一环。在你的脑海里留下了哪些算法，给你一张纸和笔，能否手到擒来，信手拈来，说来就来？

就现在，你能写出归并排序吗？能写出快速排序吗？全排列的解法呢？还有二叉树的非递归前中序遍历？…

有句成语，死去活来，我想确实需要先”死记硬背“下那些经典的东西，你才能在实际场景”灵活自如”。

所以，阿清决定接下来和大家一起将一些经典算法印入骨髓，将它们内化成身体的一部分。

今天的主题是二分查找及其变种。

今天介绍二分查找的三个代码：查找一个数、查找左边界、查找右边界。

—

查找一个数

大家都听过二分查找算法，但要想准确的写出二分查找，还是需要关注几个细节。

分别是起始位置定义与边界判断。

我们都知道数组的索引是从0开始的，即数组arr储存数据的位置包括：0，1，2，… , arr.length – 1

在定义二分查找时，我们都会定义low与high分别代表，数组的起始左边界与起始右边界。

在这里，要注意定义的起始位置。即 high = arr.length 还是 high = arr.length – 1 ?

若 high = arr.length , 循环的判断条件就为 low < high , 即当low = high 时，跳出循环。

若 high = arr.length – 1, 循环的判断条件就为 low <= high , 即当low > high 时，跳出循环。

先来看 high = arr.length – 1的代码：

public int binarySearch(int[] arr, int target) { 
 int ans = -1;
    int low = 0;
    int high = arr.length - 1;
    int mid;
    while (low <= high) {
        mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            ans = mid;
            break;
        } else if (arr[mid] > target) {
            high = mid - 1;
        } else if (arr[mid] < target) {
            low = mid + 1;
        }
    }
    return ans;
}

再来看 high = arr.length的代码：

public int binarySearch(int[] arr, int target) { 
 int ans = -1;
    int low = 0, 
    // 注意！
    int high = arr.length;
    int mid;
    // 注意！
    while (low < high) {
        mid = low + (high - low) / 2;
        if (arr[mid] == target) {
            ans = mid;
            break;
        } else if (arr[mid] > target) {
            // 注意！
            high = mid; 
        } else if (arr[mid] < target) {
            low = mid + 1;
        }
    }
    return ans;
}

上面这块代码中注释的几处地方，就是与 high = arr.length – 1不同的地方。

当定义high = arr.length – 1时，你定义的是一个闭区间，

而当定义high = arr.length时，你定义的是一个左闭右开的区间。

针对你定义的区间，在迭代中，每一个子区间应与你最开始定义的区间保持一致。

在这里，阿清不做过度的描述，大家可以针对上面两段代码，选择一个用例，自己一步一步调试，当你记住一个后，另外一个就很容易记了。

—

查找左边界

如何查找某个数在数组中左边界，注意两个点：

1、在找到target时，应继续向左边探寻它的位置，

2、在循环退出来时，应判断当前位置是否还是数组的有效索引，若是，则找到左边界，若不是，则找到右边界。

以下代码以 mid = ans.length 为例：

public int leftBound(int[] arr, int target) { 
 int ans = -1;
    int low = 0, 
    int high = arr.length - 1;
    int mid;
    while (low <= high) {
        mid = low + (high - low) / 2;
        // 与 查找一个数 不同的是 当找到target之后，接着向左缩短区间
        if (arr[mid] == target) {
            high = mid - 1; 
        } else if (arr[mid] > target) {
            high = mid - 1
        } else if (arr[mid] < target) {
            low = mid + 1;
        }
    }
    // 当low = arr.length时，说明数组中的数都小于target 没找到左边界 
    // 当 low < arr.length时，且arr[low] 不等于target，则说明没找到左边界
    if (low == arr.length || tartet != arr[low]) {
        return -1;
    }
    return low;
}

—

查找右边界

那查找右边界，其实与查找边界类似，无非就是要更改查找左边界那段代码中注释的两个地方。

我们直接看代码：

public int rightBound(int[] arr, int target) { 
 int ans = -1;
    int low = 0, 
    int high = arr.length - 1;
    int mid;
    while (low <= high) {
        mid = low + (high - low) / 2;
        // 与 查找一个数 不同的是 当找到target之后，接着向右缩短区间
        if (arr[mid] == target) {
            low = mid + 1; 
        } else if (arr[mid] > target) {
            high = mid - 1
        } else if (arr[mid] < target) {
            low = mid + 1;
        }
    }
    // 当high < 0时，说明数组中的数都大于target 
    // 当high > 0时，且arr[high]不等于target，则说明没找到右边界
    if (high < 0 || target != arr[high]) {
        return -1;
    }
    return high;
}