vlambda博客
学习文章列表

先复习一下经典二分查找题目，用C++重新刷了一遍，更新了题解和易错点：

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

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

示例 2:
输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1

提示：
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。

「题解」

• 经典binarySearch，很多题以此为基础展开
• 计算 mid 时需要防止溢出:代码中 left + (right - left) / 2 就和 (left + right) / 2 的结果相同，但是有效防止了 left 和 right 太大直接相加导致溢出
• 二分搜索如下：设置left和right俩指针，满足left <= right进入循环。mid = left + (right - left) / 2，如果mid索引对应的值刚好为target，那么直接返回；如果mid索引对应的值>target，那么搜索区间左移，right=mid-1；反之搜索区间右移，left=mid-1。直到找到该数字，就返回mid即其索引。如果跳出循环时还找不到该值就返回-1

「易错点」

• 为了防止漏下类似[5]这样的输入case，设置while条件应有等号：while (left <= right)，否则输出为-1而非0会出现Wrong Answer
• int right = nums.size() - 1;  漏掉-1会出现错误heap-buffer-overflow错误

「AC代码」

class Solution {
public:
    int search(vector<int>& nums, int target) 
    {
        // 二分查找，设置left和right俩指针
        int left = 0;
        // 设置右指针指向最后一个元素的索引
        int right = nums.size() - 1;
        while (left <= right)
        {
            // 计算中间索引
            int mid = left + (right - left) / 2;
            // 如果中间索引的值等于目标值,返回中间索引
            if (nums[mid] == target)
                return mid;
            // 如果中间索引的值大于目标值,则搜索左半边
            else if (nums[mid] > target)
                right = mid - 1;
            // 如果中间索引的值小于目标值,则搜索右半边
            else
                left = mid + 1;
        }
        // 没找到返回-1
        return -1;
    }
};

This browser does not support music or audio playback. Please play it in Weixin or another browser.

278. First Bad Version

278. 第一个错误的版本

「题解」

• 同704. 二分查找经典二分查找题，不过704不一定找得到那个数，本题一定找得到第一个出错的版本
• 当一个版本为正确版本,则该版本之前的所有版本均为正确版本;当一个版本为错误版本,则该版本之后的所有版本均为错误版本;所以可以利用上述性质进行二分查找:

1. 将左右边界分别初始化为1和n-1,其中n是给定版本的数量

2. 设定左右边界后,每次根据左右边界找到中间版本,检验其是否为正确版本:

   
   






1. 如果该版本为正确版本,那么第一个错误的版本必然在该版本右侧,因此将左边界移动到该版本右侧;

   
   

2. 否则第一个错误的版本必然位于该版本及该版本的左侧,因此将右边界移动到该版本左侧





• 每次移动边界时左右边界距离都变为原来一半,因此我们最多只需要缩O(logn)次

「易错点」

while (left <= right) 如果不取等号,输入case为5,4时输出为3(WA),而非正确答案4——704同理：为了不漏掉这个左右指针重合的情况,所以while (left <= right)中的等号不能遗漏,否则无法通过输入case为[5]这样的情况

「其他」

• 704的右指针int right = nums.size() - 1;漏掉-1会出现错误heap-buffer-overflow错误
• 本题的右指针int right = n - 1;有没有-1都可以AC

「AC代码」

// The API isBadVersion is defined for you.
// bool isBadVersion(int version); 

class Solution {
public:
    int firstBadVersion(int n) 
    {
        int left = 0;
        int right = n - 1;  // 有没有-1都可以AC
        /*
        为了不漏掉这个左右指针重合的情况,所以while (left <= right)中的等号不能遗漏,否则无法通过输入case为[5]这样的情况
        */
       while (left <= right)  // 如果不取等号,输入case为5,4时输出为3(WA),而非正确答案4
       {
           int mid = left + (right - left) / 2;
           if (isBadVersion(mid))
           {
               right = mid - 1;
           }
           else
           {
               left = mid + 1;
           }
       }
       return left;    
    }
};

「复杂度」

• 时间复杂度O(logn)，n是给定版本的数量
• 空间复杂度O(1)