山东建设住建厅网站,哪些网站设计好,一般网站建设公司好,网站策划总结精于结构、敏于心智、熟于代码 方式#xff1a;对于会的代码#xff1a;学会以最快的速度构建#xff0c;并以最快的速度书写#xff1b;对于不会的代码#xff1a;学会#xff08;以最短的路径下#xff09;看懂别人的代码。学会使用参考文档、熟悉每一个容器。
刷题位…精于结构、敏于心智、熟于代码 方式对于会的代码学会以最快的速度构建并以最快的速度书写对于不会的代码学会以最短的路径下看懂别人的代码。学会使用参考文档、熟悉每一个容器。
刷题位置「算法」 - 学习计划 - 力扣LeetCode全球极客挚爱的技术成长平台 对于二分查找问题的基础解决思路特点遍历都可以进行解决 问题时间复杂度相较于过大 查找的过程本质就是排除的过程。一次排除一批抓紧题目所给的关键特点。排列方式查询特点以while循环查找 找到了 / 确定查找范围的边界。循环结束的条件704. 二分查找 给定一个 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针对于本题 关键点我们需要在一个升序的数组中找到一个值是否存在。 核心 可以通过左小右大进行中间位置的log2的缩小范围。left的范围跟新为 mid 1right的范围跟新为 mid 1。整个范围找完即 left right 此时无该值。特殊点 只有一个值的时候 / right 更新 (mid - 1) left恰好值是left位置对left同理 - while循环增加一个left right是至关重要的。防止数组大小为空此题说了size 1此处就没事。最好别写为mid (right left) / 2因为有 (right left) 会导致数据过大。 class Solution {
public:int search(vectorint nums, int target) {// 保证比较的位置是有效数据段中的中间位置int left 0, right nums.size() - 1;int mid right / 2;//if(nums.empty())// return -1;// 左的下标大于右即有效数据段比完了left right// 防止出现只有一个数据、如right mid 1 left - nums[left] target的时候。while(left right){// 移动左右下标到有效区域if(nums[mid] target)left mid 1;else if(nums[mid] target)right mid - 1;elsereturn mid;mid left (right - left) / 2;}return -1;}
};
复杂度分析 时间复杂度O(logn)其中 n 是数组的长度。 空间复杂度O(1)。
类似题
374.猜数字大小 猜数字游戏的规则如下 每轮游戏我都会从 1 到 n 随机选择一个数字。 请你猜选出的是哪个数字。如果你猜错了我会告诉你你猜测的数字比我选出的数字是大了还是小了。你可以通过调用一个预先定义好的接口 int guess(int num) 来获取猜测结果返回值一共有 3 种可能的情况-11 或 0 -1我选出的数字比你猜的数字小 pick num。1我选出的数字比你猜的数字大 pick num。 0我选出的数字和你猜的数字一样。恭喜你猜对了pick num。 返回我选出的数字。 /** * Forward declaration of guess API.* param num your guess* return -1 if num is higher than the picked number* 1 if num is lower than the picked number* otherwise return 0* int guess(int num);*/class Solution {
public:int guessNumber(int n) {int left 1, right n;int mid left (right - left) / 2;while(left right){if(guess(mid) 0)return mid;else if(guess(mid) 1)left mid 1;elseright mid - 1;mid left (right - left) / 2;}return -1;}
};
278.第一个错误的版本 你是产品经理目前正在带领一个团队开发新的产品。不幸的是你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的所以错误的版本之后的所有版本都是错的。 假设你有 n 个版本 [1, 2, ..., n]你想找出导致之后所有版本出错的第一个错误的版本。 你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。 // The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {uint64_t left 1, right n;uint64_t mid (right left) / 2;while(left right){if(!isBadVersion(mid) !isBadVersion(mid 1)){left mid 1;else if(isBadVersion(mid) isBadVersion(mid - 1))right mid - 1;elseif(isBadVersion(mid))return mid;elsereturn mid 1;mid left (right - left) / 2;}return -1;}
};
按照常见二分查找的书写上面的题肯定是可以对的但是有点过于的臃肿效率是够的但是对于程序员是不友好的所以我们可以进行优化一下。 特殊点 此处由于我们需要第一个 bool isBadVersion(version) 为对的 所以对与right我们可以right mid因为我们无法确定它是不是第一个所以我们不能排除掉它。对于left的 bool isBadVersion(version) 为错不需要即left mid 1。 一个right mid另一个left mid 1则left right时就找到了。 // The API isBadVersion is defined for you.
// bool isBadVersion(int version);class Solution {
public:int firstBadVersion(int n) {int left 1, right n;while(left right){int mid left (right - left) / 2;if(isBadVersion(mid))right mid;elseleft mid 1;}// 此时left rightreturn left;}
};
针对上述的类似写法我们还可以解决一个题。
35.搜索插入的位置 给定一个排序数组和一个目标值在数组中找到目标值并返回其索引。如果目标值不存在于数组中返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {
public:int searchInsert(vectorint nums, int target) {int left 0, right nums.size();while(left right){int mid left (right - left) / 2;if(target nums[mid])right mid;elseleft mid 1;}// left rightif(left nums[left - 1] target)return left - 1;return left;}
};
