钟昱丰的博客

@TOC
常用的二分查找包括：寻找一个数、插入target、寻找左右边界。

第一题（寻找一个数）

704. 二分查找

题目描述：
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例1：

输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

思路

二分法，如果找到target，直接返回；如果target比中点值小，说明在左区间，则缩小右端点；如果target比中点值大，说明在右区间，则缩小左端点。

代码

c++版本

int binarySearch(vector<int> nums, int target) 
{
	// 查找区间
    int l = 0; 
    int r = nums.size() - 1;
    // 终止条件
    while(l <= r) 
    {
    	// 中点计算
        int m = l + (r - l) / 2;
        // 区间缩减
        if(nums[m] == target)
            return m; 
        else if (nums[m] < target)
            l = m + 1;
        else if (nums[m] > target)
            r = m - 1;
    }
    return -1;
}

java版本

class Solution {
    public int search(int[] nums, int target) {
        // 左闭右闭
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){
            // 防止溢出
            int m = l + (r - l) / 2;
            if(target == nums[m]){
                // 如果找到，直接返回
                return m;
            }
            else if(target > nums[m]){
                // 右边界缩小
                r = m - 1;
            }
            else if(target > nums[m]){
                // 左边界缩小
                l = m + 1;
            }
        }
        // 未找到，返回-1
        return -1;
    }
}

python版本

class Solution:
    def search(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if target == nums[m]:
                return m
            elif target < nums[m]:
                r = m - 1
            else:
                l = m + 1
        return -1

总结

本题有两点需要注意。
第一点，搜索区间是“左闭右闭”。之所以选择“左闭右闭”的搜索区间，是为了在缩小左、右端点的时候可以统一操作。此外，因为搜索区间是“左闭右闭”的，所以循环条件是左端点小于等于右端点。
第二点，取中点的计算要防溢出。

第二题（插入target）

35. 搜索插入位置

题目描述：
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为 O(log n) 的算法。

示例1：

输入: nums = [1,3,5,6], target = 2
输出: 1

思路

如果找得到，则参考上题代码。如果找不到，循环停止时，左边界l以左（不包含l）的元素都小于target，右边界r以右（不包含r）的元素都大于target。所以，target应该插入左边界l的位置，这样其左侧元素皆小于target，其右侧元素皆大于target。

代码

java版本

class Solution {
    public int searchInsert(int[] nums, int target) {
        // 左闭右闭
        int l = 0;
        int r = nums.length - 1;
        while(l <= r){
            // 防止溢出
            int m = l + (r - l)/2;
            if(target == nums[m]){
                // 如果找到，直接返回
                return m;
            }
            else if(target > nums[m]){
                // 右边界缩小
                r = m - 1;
            }
            else if(target > nums[m]){
                // 左边界缩小
                l = m + 1;
            }
        }
        // 返回左边界
        return l;
    }
}

python版本

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if nums[m] == target:
                return m
            elif target < nums[m]:
                r = m - 1
            else:
                l = m + 1
        return l

总结

循环停止时，左边界l以左（不包含l）的元素都小于target，右边界r以右（不包含r）的元素都大于target。所以，target应该插入左边界l的位置，这样其左侧元素皆小于target，其右侧元素皆大于target。

第三题（寻找左右边界）

34. 在排序数组中查找元素的第一个和最后一个位置

题目描述：
给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

思路

先考虑左边界。和前面两题不同，这题找到target不能直接返回，要继续寻找，直到找到第一个target。当循环停止时，左边界l以左的元素都小于target，则左边界l以右的元素都大于等于target，左边界l即第一个target。所以，当找到target的时候，仍然缩小右边界，向左边界靠拢。

同理，搜索右边界时，当找到target不能直接返回，要继续寻找，直到找到最后一个target。当循环停止时，右边界r以右的元素都大于target，则右边界r以左的元素都小于等于target，右边界r即最后一个target。所以，当找到target的时候，仍然缩小左边界，向右边界靠拢。

得到了左右边界，也只是说明如果有target，那第一个和最后一个target就是左右边界。但是，存在没有target的可能，所以还需要对左右边界进行判断。值得注意的是，可能target比所有的元素都大，此时左边界l等于数组长度，需要先判断是否越界，再判断左边界是否为target。同样的，可能target比所有的元素都小，此时右边界l等于-1，需要先判断是否越界，再判断右边界是否为target。

代码

java版本

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int results[] = new int[]{-1, -1};
        // 左闭右闭
        int l = 0;
        int r = nums.length - 1;
        // 寻找第一个target
        while(l <= r){
            // 防止溢出
            int m = l + (r - l) / 2;
            // 缩小右边界
            if(target <= nums[m]){
                r = m - 1;
            }
            // 缩小左边界
            else if(target > nums[m]){
                l = m + 1;
            }
        }
        // 防止越界
        if((l < nums.length) && (nums[l] == target)){
            results[0] = l;
        }
        // 左闭右闭
        l = 0;
        r = nums.length - 1;
        // 寻找最后一个target
        while(l <= r){
             // 防止溢出
            int m = l + (r - l) / 2;
            // 缩小左边界
            if(target >= nums[m]){
                l = m + 1;
            }
            // 缩小右边界
            else if(target < nums[m]){
                r = m - 1;
            }
        }
        // 防止越界
        if((r >= 0) && (nums[r] == target)){
            results[1] = r;
        }
        return results;
    }
}

python版本

class Solution:
    def searchRange(self, nums: List[int], target: int) -> List[int]:
        if nums == None or len(nums) == 0:
            return [-1, -1]
        
        result = [-1, -1]

        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if target <= nums[m]:
                r = m - 1
            else:
                l = m + 1
        
        if l < len(nums) and nums[l] == target:
            result[0] = l
        
        l, r = 0, len(nums) - 1
        while l <= r:
            m = l + (r - l) // 2
            if target >= nums[m]:
                l = m + 1
            else:
                r = m - 1
        
        if r >= 0 and nums[r] == target:
            result[1] = r

        return result

总结

本题有三点需要注意。

第一点，理解为什么左右边界就是第一个和最后一个target。当循环停止时，左边界l以左的元素都小于target，则左边界l以右的元素都大于等于target，左边界l即第一个target。当循环停止时，右边界r以右的元素都大于target，则右边界r以左的元素都小于等于target，右边界r即最后一个target。

第二点，当找到target的时候左右边界如何移动。寻找左边界时，需要右边界向左边界靠拢，所以找到target时仍然缩小右边界。寻找右边界时，需要左边界向右边界靠拢，所以找到target时仍然缩小左边界。

第三点，防止左右边界越界。左右边界是target“应该”出现的第一个和最后一个位置，到底是不是还需要经过验证。验证之前，记得考虑左右边界是否越界。

下一篇博客LeetCode算法题解——二分查找2，我将总结LeetCode中部分题目的二分查找解法。

参考:

二分查找算法细节详解，顺便写了首诗