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

704. 二分查找

力扣

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
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： 

1
2
3
4
5
6
7
8
9
10
11
12
13

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  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. 移除元素的全部内容，更多相关代码随想录算法训练营第一天|内容请搜索靠谱客的其他文章。