二分查找
题目链接：二分查找
思路：对于闭区间要注意判断条件：while (left <= right) 要使用 <= ，因为left == right是有意义的
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size()-1;
while(left <= right)
{
int middle = left + ((right - left)/2); //防止溢出
if(nums[middle] > target)
{
right = middle -1;
}else if (nums[middle] < target)
{
left = middle + 1;
}else{
return middle;
}
}
return -1;
}
};
思路：对于左闭右开:注意判断条件已经不是<= 而是小于，当middle > target时，right = middle (右开区间取不到）
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while(left < right)
{
int middle = left + ((right - left) >> 1);
if(nums[middle] > target)
{
right = middle;
}else if (nums[middle] < target)
{
left = middle + 1;
}else{
return middle;
}
}
return -1;
}
};
移除元素
题目链接：移除元素
思路：快指针：指向新元素 ；慢指针：更新数组
1、不改变元素相对位置
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slowIndex = 0;
for(int fastIndex = 0;fastIndex < nums.size(); fastIndex++){
if(val != nums[fastIndex]){
nums[slowIndex++] = nums[fastIndex];
}
}
return slowIndex;
}
};
2、可以改变位置 减少移动元素次数
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int leftIndex = 0;
int rightIndex = nums.size() - 1;
while(leftIndex <= rightIndex){
while(leftIndex <= rightIndex && nums[leftIndex] != val){
++leftIndex;
}
while(leftIndex <= rightIndex && nums[rightIndex] == val){
-- rightIndex;
}
if(leftIndex < rightIndex){
nums[leftIndex++] = nums[rightIndex--];
} //将右边不等于val的元素覆盖左边等于val的元素
}
return leftIndex; //leftIndex一定指向了最终数组末尾的下一个元素
}
};
总结：1、二分法注意在区间右开的情况下，判断条件要改，以及当目标值在左侧的情况下改成right = middle，不用加一
2、双指针法在多种类型题目都有用到，还需要巩固串在一起再看看，注意第二种改变元素位置以减少元素移动次数的方法
3、防止空间溢出时采用 left +（right-left）/2
4、位运算>>1 为/2 ，可提高效率
