二分查找的区间选择问题（不断更新中）

Leetcode刷题
留言

二分查找是一种十分基础重要的搜索方法。一般多用于数组结构的搜索查找问题中。虽然思路简单，但是边界条件却很容易让人迷糊。这里对二分查找做一个总结。

首先以35题简单题做一个示范：

35 搜索插入位置](https://leetcode-cn.com/problems/search-insert-position/))

题目描述

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

你可以假设数组中无重复元素。

示例 1:

输入: [1,3,5,6], 5

输出: 2

示例 2:

输入: [1,3,5,6], 2

输出: 1

示例 3:

输入: [1,3,5,6], 7

输出: 4

示例 4:

输入: [1,3,5,6], 0

输出: 0

做题思路

这道题的思路非常简单，就是利用二分查找，不断更新边界，最后锁定到某个插入位置。下面介绍两种具体写法中边界的不同考虑。

写法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {

        int size = nums.size();
        int left = 0, right = size-1;   // 右指针指在最后一个元素上

        while (left <= right)   // 因为左右指针都指在一个确定的数字上，所以存在两个指针指在同一个数字的情况
        {
            int mid = left + (right-left)/2;    // 这种方式避免溢出

            if(nums[mid]==target)
                return mid;
            else if (nums[mid]<target)
            {
                left = mid+1;   // 左右指针都指向确切的元素，所以当mid不满足时变换左右指针应该变到下一个位置
            }else{
                right = mid-1;  // 同理。
            }
        }
        return left;    // 这种情况下left靠后
        
    }
};

这种写法的关键在于左右边界所指的元素都在要考虑的区间内，也就是一种闭区间的写法，每次考虑的是[left,right]的情况，为了避免考虑过的区间重新考虑，我们就要在更新边界时将mid+1或者-1来赋值区间边界。

写法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {

       int size = nums.size();
       int left = 0,right = size;   //右指针指在不存在的元素

       while (left < right) // 不存在左右指针指在同一个元素的情况
       {
           int mid = left + (right-left)/2;

           if(nums[mid]==target){
               return mid;
           } else if (nums[mid]<target) {
               left = mid+1;    // 左指针指在确切元素，所以+1
           } else {
               right = mid; // 右指针所指的元素不会考虑，所以mid
           }
       }
       return right;     // 这种情况下right靠后
        
    }
};

这种写法的关键在于右边界所指的元素并不在要考虑的区间内，是一种半开闭的区间状态，每次考虑的是[left,right)的情形。所以此时在更新状态时，更新右边界时直接让右边界等于mid就好，因为mid已经考虑过了。

当然在很多时候，像这样直白地告诉你我就是二分查找的题目并不是很多，再举一个二分查找解决的简单题，leetcode第69题，据说是一个常见的面试题目。

69 x-的平方根

题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1：

输入：4

输出：2

示例 2：

输入：8

输出：2

说明：8的平方根是2.82842…… 由于返回类型是整数，所以小数部分将会被舍去。

做题思路

本题其实是一个二分查找的典型应用场景，虽然看不到数组，但是显然自然数本身就是一个单调有序的排列，而x就是上界，0就是下界。这是因为因为题中提到小数部分会被舍去，同时，如果一个数的平方大于x，则它必然不可能是x的平方根。

这样这道题可以转换为，在数组[0,1,···,x]中，查找其中某个数的平方等于x，如果没有数的平方等于x，则找出平方小于x中最接近x的数。

这样看就是一个显然的二分查找了。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int mySqrt(int x) {
        int right=x;	// 右边界，因为任何一个数的平方根必然小于等于某个数
        int left=0;		// 左边界
        while (left<=right)		// 同前，闭区间边界条件有数
        {
            int mid = left + (right-left)/2;
            if ((long long)mid*mid==x)		//需要强转一下，因为可能溢出
            {
                return mid;
            } else if ((long long)mid*mid < x)		// 强转防止溢出
            { 
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
        return right;		// 不同于上面我们需要的是偏前的位置，此时right在左left在右，所以返回right
        
    }
};

以上两道题可以理解为二分查找找一个数的题目，接下来是一道二分查找找两个数的题目

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

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

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

进阶：

你可以设计并实现时间复杂度为 O(log n) 的算法解决此问题吗？

示例 1：

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

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

  • $ 0 <= nums.length <= 105$
  • $-10^9 <= nums[i] <= 10^9$
  • nums 是一个非递减数组
  • $-10^9 <= target <= 10^9$

做题思路

思路上没有特别新鲜的地方，这道题的题解有趣之处在于函数的复用。具体思考见注释。

解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    // 二分过程
    // 输入：数组、目标元素、目标元素重复出现的左右边界标志变量  true--左边界  false--右边界  
    int binarySearch(vector<int>& nums, int target, bool lower) {
        // 二分的左右边界赋值。边界值初始化为数组大小（不是数组最后一位）
        int left = 0, right = (int)nums.size() - 1, ans = (int)nums.size();
        while (left <= right) {
            int mid = (left + right) / 2;
            //// 当mid指的数大于target，说明目标区域在左侧
            // 而当mid指的数等于target，且同时要找的是左边界时，就不排除当前mid所指的数就是目标区域左边界（此时是有可能左右边界重合）
            if (nums[mid] > target || (lower && nums[mid] == target)) {     
                right = mid - 1;
                ans = mid;
            } else {
                // 当mid指的数小于target，或者找的是右边界且mid等于target，则不需要调整ans位置，因为ans本来就处在目标区域的最右边。
                left = mid + 1;
            }
        }
        return ans;
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        int leftIdx = binarySearch(nums, target, true);         // 使用二分查找找第一次出现
        int rightIdx = binarySearch(nums, target, false) - 1;   // 使用二分查找找最后一次出现
        // 如果第一次出现小于等于第二次出现、最后一次出现小于数组大小、并且两次出现确实都是target，则可以返回
        if (leftIdx <= rightIdx && rightIdx < nums.size() && nums[leftIdx] == target && nums[rightIdx] == target) {
            return vector<int>{leftIdx, rightIdx};
        } 
        // 否则返回[-1,-1]
        return vector<int>{-1, -1};
    }
};