我的网站百度怎么搜索不到了,优化大师卸载不了,大连网站建设信息,网站建设方案书设计图第一个错误的版本 题目及要求二分查找 题目及要求
你是产品经理#xff0c;目前正在带领一个团队开发新的产品。不幸的是#xff0c;你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的#xff0c;所以错误的版本之后的所有版本都是错的。
假设你… 第一个错误的版本 题目及要求二分查找 题目及要求
你是产品经理目前正在带领一个团队开发新的产品。不幸的是你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的所以错误的版本之后的所有版本都是错的。
假设你有 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
提示
1 bad n 231 - 1
二分查找 思路根据题目描述得知有序使用二分查找不断缩减范围 isBadVersion 函数会接受一个版本号作为参数并返回一个布尔值来指示该版本是否有问题。例如如果 isBadVersion(3) 返回 true则表示版本 3 存在问题如果返回 false则表示版本 3 没有问题 // The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {int i1,jn; // 初始化查找范围为 [1, n]while(ij){ // 当查找范围不为空int mi(j-i)/2; // 计算中间位置if(isBadVersion(m))jm-1; // 如果中间位置是错误版本就缩小右边界else im1; // 如果中间位置不是错误版本就缩小左边界}return i; // 返回第一个错误版本的编号}
};
