十四天算法快速入门第一天之「二分查找」

写在前面：本文题单均来自力扣的算法刷题计划，开这个系列主要是以题目与题解的形式对一些常见、常用算法进行归类和总结，希望在促进自己学习的同时也能帮助到看到这篇文章的大家。另外，本文并非一天一更~

题目一：704. 二分查找

题目描述：

题目分析：

这题主要是用于熟悉二分查找的模板，我们要找数组中某个元素的下标，用二分来就是设置一个left等于0，表示为数组的第一个，设置一个right等于数组长度减去1，表示数组的最后一个，然后进行二分：若以mid为下标的元素小于目标值，说明找小了，目标值在mid和right之间，所以让右端不变，左端left赋值为mid+1；反之一样的道理。另注：下方的题解代码是二分的左闭右闭式模板。

题解代码：

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int left =0;
        int right=nums.size()-1;
        while(left<=right)
        {
            int mid=(left+right)/2;   //left+((right-left)/2)
            if(nums[mid]>target)
            {
               right=mid-1;
            }
            else if(nums[mid]<target)
            {
                left=mid+1;
            }
            else
            {
                return mid;
            }
        }
        return -1;
    }
};

题目二：278. 第一个错误的版本

题目描述：

题目分析：

这题的做法跟上面一题大同小异，若一段判断为：false false false true true，我们要找的就是第一个true的下标（判定为是错误的版本）。若在二分中mid判断为false说明我们要找的第一个true还在右边，所以让左边赋值为mid+1，反之让右边赋值为mid-1。

题解代码：

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

class Solution {
public:
    int firstBadVersion(int n) {
        int left=1;
        int right=n;
        int bad;
        while(left<=right)
        {
            int mid=left+((right-left)/2);
            if(isBadVersion(mid))
            {
                bad=mid;
                right=mid-1;
            }
            else
            {
                left=mid+1;
            }
        }
        return bad;
    }
};

题目三：35. 搜索插入位置

题目描述：

题目分析：

解法仍然与第一题一样，注意返回值即可。

题解代码：

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
            int left=0;
            int right=nums.size()-1;
            while(left<=right)
            {
                int mid=(left+right)/2;
                if(nums[mid]<target)
                {
                    left=mid+1;
                }
                else if(nums[mid]>target)
                {
                    right=mid-1;
                }
                else if(nums[mid]==target)
                {
                    return mid;
                }
            }
            return left;
    }
};