我们经常会遇到各种要求的二分查找，总结下来无非是三种应用场景：

• 寻找一个数
• 寻找左侧边界
• 寻找右侧边界

网上有各种模板，有各种形式，理解、记忆起来比较困难。本文针对这三种情况，提出一种模板，只需要改变2处地方，就可以应对。由于改变太少了，大家可以直接记忆下来。

2 模板讲解

2.1 寻找一个数

寻找一个数是我们最常见的一种情形，具体原理不必多说，我们直接上代码，相信大家已经熟练掌握。只要找到了这个数，那么久可以直接返回，否则就返回-1。

int binarySearch(int[] nums, int target) {
    int left = 0; 
    int right = nums.length - 1; 

    while(left <= right) { 
        int mid = (right + left) / 2;
        if(nums[mid] == target)
            return mid; 
        else if (nums[mid] < target)
            left = mid + 1; 
        else if (nums[mid] > target)
            right = mid - 1; 
        }
    return -1;
}

2.2 寻找左边界

如果给定一个数组[1,2,2,2,3],让我们查找第一个等于2的下标。我们只需要改变以下两个地方。

public int  binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; 

        while(left <= right) { 
            int mid = (right + left) / 2;
            if(nums[mid] == target)
                right = mid - 1; //1. 改变一
            else if (nums[mid] < target)
                left = mid + 1; 
            else if (nums[mid] > target)
                right = mid - 1; 
        }
        return right+1; //2. 改变二
    }

讲解： 下来我们分步进行讲解。

第一步：

left = 0, right = 4, mid = 2

此时nums[mid] == target

left = 0, right = mid - 1 = 1

第二步：

left = 0, right = 1, mid = 0

此时nums[mid] < target

left = mid + 1 = 1, right = 1

第三步：

left = 1, right = 1, mid = 1

此时nums[mid] == target

left = 1, right = mid - 1 = 0

第四步：

left > right 退出循环

说明：

nums[mid] 大于、小于的时候很容易理解。

当nums[mid]等于target的时候，由于要向求左边界，需要向左逼近，所以right = mid - 1。

当我们执行最后一步的时候肯定是nums[mid] == target，这时候right = mid - 1。因为此时mid就是我们要找的正确的位置，所以我们返回right + 1, 也就是mid的位置。

2.3 寻找右边界

与寻找左边界同理，只需要改变两个地方。其实也就是nums[mid]等于的时候向右逼近。

public  int  binarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1; 

        while(left <= right) { 
            int mid = (right + left) / 2;
            if(nums[mid] == target)
                left = mid+1; // 1 改变一
            else if (nums[mid] < target)
                left = mid + 1; 
            else if (nums[mid] > target)
                right = mid - 1; 
        }
        return left - 1; // 2 改变二
    }

3 判断是否存在

我们找到了这样一个下标，万一我们找的这个数在数组中不存在咋办。所以最后要进行判断一下。

3.1 判断左边界是否存在

// 如果所有的数都是比target小
if (r+1 == nums.length) return -1;
// 如果找到的这个数不等于target。这可能是第一个大于target的数。
return nums[r+1] == target ? r+1 : -1;

3.2 判断右边界是否存在

//如果所有的数都比target大
if (l-1 == -1) return -1;
//如果找到的这个数不等于target。这可能是第一个小于。
return nums[l-1] == target ? l-1 : -1;

4 写在最后

二分查找在算法题中的应用还是很多的，比枚举能够有效的减少时间复杂度。基本上没有题目会让大家单纯的去找左右边界，但是这种思想会以各种变形出现在各种题目中。后面的文章中我们会给大家指出。