代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素

704. 二分查找

力扣

题解：

class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int middle = (left + right) / 2;
while (left <= right)
{
if (nums[middle] > target)
right = middle - 1;
else if (nums[middle] < target)
left = middle + 1;
else if (nums[middle] == target)
return middle;
middle = left + (right - left) / 2;
}
//if (left > right)
return -1;
}
};

笔记：

1. 使用二分法的条件：数组有序且不重复;
2. 二分公式：

middle = left + (right - left ) / 2；//防止left + right大于intmax导致不执行/2

if(nums[middle] > target)

         right = middle - 1;

else if(nums[middle] < target)

        left = middle + 1;

     3.二分模板：力扣 

Q： 

while (left <= right)
{
if (nums[middle] > target)
right = middle - 1;
else if (nums[middle] < target)
left = middle + 1;
else if (nums[middle] == target)
return middle;
middle = left + (right - left) / 2;
}
//if (left > right)
return -1;

为何多了一句

 if(left > right)   

就显示编译不通过，但是在VS上跑时可以通过。

A：加入if语句时会判断else的情况，所以编译时会显示没有返回值的情况，VS默认返回值为0，所以不会出现编译不通过的情况。

27. 移除元素

笔记：

1.暴力解法中，循环的终止条件使用剩余数组的长度，否则超时

2.双指针法：

定义快慢指针

• 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
• 慢指针：指向更新 新数组下标的位置

  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;
  }
  };

  注意：

        数组元素与目标元素不相等时，快慢指针一起运动；数组元素与目标元素相等时，慢指针不运动

最后

以上就是仁爱滑板为你收集整理的代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素的全部内容，希望文章能够帮你解决代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。