个人主页https://github.com/zbhgis前言本系列主要记录自己学习算法的过程中的感悟。第一篇分析时空复杂度会比较详细一点后续都简略化。力扣704.二分查找链接https://leetcode.cn/problems/binary-search/注意点闭区间做法。这道题的题目关键在于如何判断边界条件。1.left和right的初始值。在闭区间下主要是考虑到两边都能取到值因此left和right就是原始数组的下标边界。2.在循环的时候left是否要等于right。如果是闭区间那么就是left小于等于right因为等leftright的时候区间[left, right]是成立的说明循环可以继续执行。3.循环内部的左右边界条件判断。当nums[mid] target的时候此时target是在nums[mid]的左边说明右边界需要收缩此时right mid - 1; 为啥需要减去1是因为此时是闭区间如果不减去1的话那么更新后的区间[left, mid]可是nums[mid]已经在nums[mid] target的时候已经判断过了说明nums[mid]一定不是我们需要的值所有需要将mid-1此时才能得到正确的区间[left, mid - 1]。同理当nums[mid] target的时候此时target是在nums[mid]的右边说明左边界需要收缩此时left mid 1为啥需要加1的道理同上一段只有减去1才能得到下一轮循环的正确区间[mid 1, right]。4.要注意溢出。如果mid的确定是直接通过(left right) / 2; 那么可能会溢出因为当left或right中存在一个特别大的数字的时候此时会超过int类型的取值范围。5.最终捋一下思路本质上通过对比nums[mid]与target的值不断的缩短边界从而找到所需要的值。主要是边界的判定死记硬背记不住而且后续还有很多变种题目。所以得搞懂各个题目的边界到底是怎么设计。代码class Solution {public int search(int[] nums, int target) {if (target nums[0] || target nums[nums.length - 1]) {return -1;}int left 0;int right nums.length - 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 {right mid - 1;}}return -1;}}时空复杂度分析1.时间最坏情况下每次都进行区间二分设数组长度为 n每次循环后剩余元素数第1次循环后≤ n/2第2次循环后≤ n/4第3次循环后≤ n/8第k次循环后≤ n/2ᵏ当 n/2ᵏ 1 时结束n/2ᵏ 1n 2ᵏk log₂n所以循环次数 ≤ log₂n所以时间复杂度为O(logn)2.空间都是一些常量级别的额外空间所以空间复杂度O(1)力扣35.搜索插入位置链接https://leetcode.cn/problems/search-insert-position注意点这道题的题目比较简单主要是返回值的确定。1.当nums[mid] target的时候直接返回mid就行2.当nums[mid] target与nums[mid] target的时候按照二分查找的思路一直找3.当在数组中找不到target的时候此时分为三种情况在数组前面在数组后面在数组中间但是没有对应值。这个时候的返回值就是left。因为当一直找不到数组中对应的target时经过不断地二分跳出循环的时候left在right右边此时right1 left即跳出循环后的区间为[right, left]当target在数组前面时此时right为-1left为0所以target插入位置为left当target在数组中间时此时target一定是落在一个区间内的target一定比right大比left小所以target插入为left当target在数组后面时此时left为nums.length所以target插入位置为left综上上述三种情况的返回值都是left。4.梳理一下整体还是按照二分查找去写只不过现在返回值有点不一样。尤其是上述的后三种情况经过分析是可以统一为一种返回值的也就是数组中找不到target的时候返回值是一样的。代码class Solution {public int searchInsert(int[] nums, int target) {int left 0;int right nums.length - 1;while (left right) {int mid left (right - left) / 2;if (nums[mid] target) {left mid 1;} else if (nums[mid] target) {right mid - 1;} else {return mid;}}return left;}}时空复杂度分析同上。力扣34.搜索插入位置-解法1链接https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/注意点这道题的题目基本就是经典的二分。1.这道题的前半段就是用二分查找找到那个target是否在nums中不在即可直接返回[-1, -1]2.但如果找到了target在nums中的位置接下来就得确定出left和right的具体位置。让left和right反向拓展。3.边界条件中因为涉及到left–和right所以left - 1和right 1的结果均不能超出数组的下标就是代码中的left -1 -1 与 right 1 nums.length或者写成left - 1 0 与 right 1 nums.length -1 可能会更加清楚一点直到往外拓展的值都不等于target的时候就跳出循环。4.总结就是先用经典二分找到对应的target的可能下标然后对下标进行区间的扩展得到最终的结果。代码class Solution {public int[] searchRange(int[] nums, int target) {int idx binarySearch(nums, target);if (idx -1) {return new int[] {-1, -1};}int left idx, right idx;while (left - 1 -1 nums[left - 1] nums[idx]) {left --;}while (right 1 nums.length nums[right 1] nums[idx]) {right ;}return new int[] {left, right};}private int binarySearch(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid - 1; } else if (nums[mid] target) { left mid 1; } else { return mid; } } return -1; }}时空复杂度分析二分查找部分的时空复杂度分析同上但是这个解法加了一个线性扫描所以最坏情况下可能会达到O(log n n)即O(n力扣34.搜索插入位置-解法2链接https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/description/注意点这道题的题目解法一比较好理解一点解法二效率相对高一点。1.先想办法找到left就是target匹配的元素的开始位置构建一个方法getLeftBound()通过getLeftBound()得到target 1的左边界然后再减1就是target的右边界。2.写getLeftBound的时候使用闭区间的写法时需要注意的是nums[mid] target 和 nums[mid] target 这两个判断合并在一起了是进一步找到新的right。因为当nums[mid] target的时候如果直接返回mid此时的mid可能是连续多个元素的中间某一个不是最终想要的left。所以把这个情况合并给right此时nums[mid] target最终right不再进行判断时right mid left不再进行判断时left mid且left right 1。代码class Solution {public int[] searchRange(int[] nums, int target) {int left getLeftBound(nums, target);if (left nums.length || nums[left] ! target) {return new int[] {-1, -1};}int right getLeftBound(nums, target 1) - 1;return new int[] {left, right};}private int getLeftBound(int[] nums, int target) { int left 0; int right nums.length - 1; while (left right) { int mid left (right - left) / 2; if (nums[mid] target) { right mid - 1; } else { left mid 1; } } return left; }}时空复杂度分析两次二分查找所以为O(log n log n) O(log n)空间复杂度还是O(1)力扣69.x的平方根链接https://leetcode.cn/problems/sqrtx/description/注意点这道题就是跟经典二分比需要考虑边界条件的变化。1.由于是进行开方运算所以right的最大值可以设定不超过Integer的平方根此时就不要减去12.其他步骤类似就是比较条件变成了mid的平方与x进行比较了代码class Solution {public int mySqrt(int x) {int left 0;int right Math.min(x, (int) Math.sqrt(Integer.MAX_VALUE));while (left right) { int mid left (right - left) / 2; if (mid * mid x) { return mid; } else if (mid * mid x) { left mid 1; } else if (mid * mid x) { right mid - 1; } } return right; }}时空复杂度分析类似于力扣704. 二分查找力扣367. 有效的完全平方数链接https://leetcode.cn/problems/valid-perfect-square/description/注意点思路同力扣69. x的平方根代码class Solution {public boolean isPerfectSquare(int x) {int left 0;int right Math.min(x, (int) Math.sqrt(Integer.MAX_VALUE));while (left right) { int mid left (right - left) / 2; if (mid * mid x) { return true; } else if (mid * mid x) { left mid 1; } else if (mid * mid x) { right mid - 1; } } return false; }}时空复杂度分析类似于力扣704. 二分查找参考https://programmercarl.com/%E6%95%B0%E7%BB%84%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%80.html