个人主页：https://github.com/zbhgis
前言
本系列主要记录自己学习算法的过程中的感悟。
第一篇分析时空复杂度，会比较详细一点，后续都简略化。
力扣704.二分查找
链接：https://leetcode.cn/problems/binary-search/
注意点
闭区间做法。
这道题的题目关键在于如何判断边界条件。
1.left和right的初始值。在闭区间下，主要是考虑到两边都能取到值，因此left和right就是原始数组的下标边界。
2.在循环的时候left是否要等于right。如果是闭区间，那么就是left小于等于right，因为等left=right的时候，区间[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ᵏ < 1
n < 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右边，此时right+1 = left，即跳出循环后的区间为[right, left]
当target在数组前面时，
此时right为-1，left为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的平方根，此时就不要减去1
2.其他步骤类似，就是比较条件变成了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