虽然也刷了一些题了, 但是没有总结, 这样效率不高. 之后刷题都写一下总结.
LeetCode上的标记 :
- 红色 不通过
- 紫色 有待优化
- 绿色 达到期望
(easy 704. 二分查找)
?001 递归
开始用递归写了一遍, 代码写得很长
- 递归要注意target的值在哪个范围, 如果target小于最小值或者大于最大值
?002 循环
后来发现可以一个循环解决
class Solution {
public:
int search(vector<int>& nums, int target) {
//左右指针采取 双闭区间
int left = 0;
int right = nums.size() - 1;
while(left<=right)
{
int mid = (left+right)/2;
if(target<nums[mid]) right = mid - 1;
else if(target>nums[mid]) left = mid + 1;
else return mid;
}
return -1;
}
};
?总结
- 尾递归都可以用循环解决
- 如果采取 双闭区间, 上例中的这个num[mid], 奇数就是中间那个, 偶数就是中间两个靠左边那个
? 两种区间
上例假设 nums.size() = n 用索引取值的话就是取到: 0, 1, ... , n-1
我们通常使用以下两种方法来表示这个取值范围：
1.双闭区间[0,n-1]，即两个边界都包含自身；在此方法下，区间 [0,0] 仍包含个元素；(建议使用)
2.左闭右开[0,n)，即左边界包含自身、右边界不包含自身；在此方法下，区间 [0,0) 不包含元素.
C++迭代器是使用左闭右开区间 [) 的. 比如erase(), 去除一个左闭右开区间, 返回右边的元素.
在“双闭区间”表示法中，由于对左右两边界的定义相同，因此缩小区间的i和j的处理方法也是对称的，这样更不容易出错。因此，建议采用“双闭区间”的写法。(Hello 算法)