704. 二分查找
题目链接:https://leetcode.cn/problems/binary-search/
文章讲解:https://programmercarl.com/0704.二分查找.html
简单的二分查找法,核心是认识区间的意义,注意以下几点:
- middle=low+(low+high)/2;这种写法可以防止溢出。
- 注意low和high的循环条件判断,如果是左闭右闭的区间,则为low<=high,否则为low<high(左闭右开区间)
- 注意high的取值,若为左闭右闭的区间,则为right=middle-1;否则为right=middle(左闭右开区间)
点击查看代码
class Solution {
public:
int search(vector<int>& nums, int target) {
int low = 0, high = nums.size() - 1;
int middle;
while (low <= high) {
middle = low + (high - low) / 2;
if (nums[middle] == target)
return middle;
else if (nums[middle] < target) {
low = middle + 1;
continue;
} else if (nums[middle] > target) {
high = middle - 1;
continue;
}
}
return -1;
}
};
27. 移除元素
题目链接:https://leetcode.cn/problems/remove-element/
文章讲解:https://programmercarl.com/0027.移除元素.html
删除有序数组中重复项,用双指针,ez
点击查看代码
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int del=0;
int s=nums.size();
for(int i=0;i<nums.size();i++)
if(nums[i]==val)
{
del++;
}
else
{
nums[i-del]=nums[i];
}
return s-del;
}
};