网站建设资源kindle,做推广网站排名,珠海响应式网站建设公司,网站登录页面怎么做二分查找题解
一、碎碎念
从本周开始#xff0c;重新更新刷题记录了哈。 基于费曼学习法的原理#xff0c;最好的输入是输出#xff0c;所以与大家分享。 鉴于目前这个糟糕的市场环境#xff0c;还是要练好自己的基本技术#xff0c;万一那天就被迫 N 1了#xff0c;你…二分查找题解
一、碎碎念
从本周开始重新更新刷题记录了哈。 基于费曼学习法的原理最好的输入是输出所以与大家分享。 鉴于目前这个糟糕的市场环境还是要练好自己的基本技术万一那天就被迫 N 1了你说是吧。
Leetcode 两年没见出了个分块刷题的区域。甚好就照着这个边刷边给各位分享吧。
二、正文
1. 简介
二分算法是一个比较常用的基础算法。 本期分享的是两道简单题重点在于解析二分算法的原理和注意点而不在于难度。
2.算法原理
二分算法的原理很简单顾名思义。 是将一组有序数据从中间二分循环比较中值根据中值和目标值的比较来决定最右边左移还是最左边右移后进入下一个循环或者满足退出条件后退出循环。
好那么开始提炼关键点。 首先得是有序数据只有有序中值的比较才有意义。不然中值的左右两边都比中值大或者小。鬼知道移动最左边还是最右边。
二要根据中值和目标值的比较来确定是否进入下一个循环或者退出。也就是确定退出条件。这个就要看清楚题干中的条件了。诸如升序降序和目标值相等还是小于某个值的最下值
最后还有几个注意点在代码分析时讲解。
3.代码实操
题目 给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果目标值存在返回下标否则返回 -1。
func search(nums []int, target int) int {l, r, m, num : 0, len(nums)-1, 0, 0for l r {m (r - l)/2 lnum nums[m]if num target {return m} else if num target {r m - 1} else {l m 1}}return -1
}代码不复杂仔细研究下凭借各位的聪明才智肯定能读懂。但有几个隐藏的注意点需要关注。
首先循环遍历时最左边要小于等于右边。这个等于很关键因为二分分到非整值时是自动取小的数的。有可能遍历到最后就俩值。先遍历到了小的但目标是大值等你右移的话假如没等于号那你就退出循环了没找到目标值报错咯。
然后要注意中值的取法。应该是最右边减最左边的一半加上最左边。因为起点不是 0而是最左边。你要找的是最左边与最右边的中值。
最后移动边界时。不必取中值本身。这个倒是取决于题干的本题不取是因为找等于目标值的对象。中值没取到就可以被过滤但其他情况可能就不一样了具体情况具体分析。
下面再浅浅分析一个变种。
【Leetcode 278】 第一个错误版本 题目 你是产品经理目前正在带领一个团队开发新的产品。不幸的是你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的所以错误的版本之后的所有版本都是错的。
假设你有 n 个版本 [1, 2, …, n]你想找出导致之后所有版本出错的第一个错误的版本。
你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。
/** * Forward declaration of isBadVersion API.* param version your guess about first bad version* return true if current version is bad * false if current version is good* func isBadVersion(version int) bool;*/func firstBadVersion(n int) int {l, r, m, tar : 1, n, 0, 0for l r {m (r-l)/2 lif isBadVersion(m) {r m - 1if tar m || tar 0 {tar m} else {break}} else {l m 1}} return tar
}本题变在并不是匹配上接口要做的是找到判定为 false 的最小值。 你就需要用一个值来暂存这个返回值。然后不断二分直到找不到比他更小的值为止。 所以你的退出条件不是匹配到 true 就退出而是找不到比他更小的 true 再退出。等于或者大于都退出。
end
