力扣-14天算法入门
第1天 二分查找
第2天 双指针
第3天 双指针
第4天 双指针
第5天 双指针
第6天 滑动窗口
第7天 广度优先搜索 / 深度优先搜索
第8天 广度优先搜索 / 深度优先搜索
第9天 广度优先搜索 / 深度优先搜索
第10天 递归 / 回溯
第11天 递归 / 回溯
第12天 动态规划
第13天 位运算
第14天 位运算
力扣-第1天 二分查找
前言
本系列文章是我的力扣刷题记录,采用c++进行编写
一、二分查找-查找一个数
难度(简单)
题目:给定一个 n 个元素有序的(升序)整型数组 nums 和一个目标值 target ,写一个函数搜索 nums 中的 target,如果目标值存在返回下标,否则返回 -1。
分析:
根据题意这里是让我们找到 一个数组中的一个数,找到就返回该数在数组中的下标,数组中没有这个数就返回-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-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;
}
};
二、二分查找-第一个错误的版本
难度(简单)
题目:你是产品经理,目前正在带领一个团队开发新的产品。不幸的是,你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的,所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n],你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
示例 1:
输入:n = 5, bad = 4
输出:4
解释:
调用 isBadVersion(3) -> false
调用 isBadVersion(5) -> true
调用 isBadVersion(4) -> true
所以,4 是第一个错误的版本。
示例 2
输入:n = 1, bad = 1
输出:1
分析:
这一题和第一题大同小异,但这里要注意的是,当前版本是正确的话,后面的都是正确的。
我们对中间版本进行判断如果中间版本正确就令right = mid,否则就另left = 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;
while(left<right){
int mid = left + (right - left) / 2;
if (isBadVersion(mid))
{
right = mid;
}
else
{
left = mid+1;
}
}
return left;
}
};
三、二分查找-搜索插入位置
难度(简单)
题目:给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。
具体代码如下:
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-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 left;
}
};
总结
期待大家和我交流,留言或者私信,一起学习,一起进步!