704. 二分查找
题目链接：https://leetcode.cn/problems/binary-search/ 视频链接：https://www.bilibili.com/video/BV1fA4y1o715 文章讲解：https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html卡哥的题目建议： 大家能把 704 掌握就可以，35. 搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置 ，如果有时间就去看一下，没时间可以先不看，二刷的时候在看。先把 704写熟练，要熟悉 根据 左闭右开，左闭右闭 两种区间规则 写出来的二分法。
做题思路：
1，先了解什么是二分查找：二分查找也称折半查找（Binary Search)。 2，再了解折半查找的实现原理：假设我们在有三个数的有序数组中查找一个目标数，这个目标数我们一开始也不知道是有序数组中的哪个数，只能通过把目标数与有序数组的中间数进行比较，进一步缩小范围（见下面的 3）来找到目标数。如果目标数比中间的数大，则在有序数组的后半部分进行查找；如果目标数比中间数小，则在有序数组的前半部分进行比较；如果相等，则找到了比较元素的位置。折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序（升序降序都可，我们默认升序）排列。3，确定在哪个范围里比较和查找，一开始大范围是在整个数组，当比较完了，我们就知道在前半部分或者后半部分的小范围里查找，还要更新小范围的边界值，在小范围里比较再细分成更小的范围，如此类推.........,这个范围数学化理解就是区间，区间可以分为左闭右闭，左闭右开，（这两种区间用得多），我自己比较好理解左闭右闭这种方式的。
我没用力扣的环境运行，用的是vs，看了视频后，就差不多能理解代码了，用左闭右闭方式的完整代码如下：
1 #include <iostream>
2 using namespace std;
3 const int N = 10;
4 int a[N]; //声明全局数组
5 int BinarySearch(int a[], int target)
6 {
7 int left = 0, right = sizeof(a) - 1; //左闭右闭区间范围为[left, right]，即[0, n-1],left,right，也是数组下标
8 int middle; //数组的中间数的下标
9 while (left <= right) //在一个合法的区间里比较和查找，比如[1, 1]，这个区间只有1，合法
10 {
11 middle = left + (right - left) / 2; //防止溢出 等同于(left + right)/2
12 if (target < a[middle]) //查找范围在数组的前半部分
13 {
14 right = middle - 1;//因为区间是左闭右闭，所以前半部分的右边界值不包含middle
15 }
16 else if (target > a[middle]) //查找范围在数组的后半部分
17 {
18 left = middle + 1;//因为区间是左闭右闭，所以后半部分的左边界值不包含middle
19 }
20 else if (target == a[middle])//目标数和数组中间数相等
21 {
22 return middle; //直接输出数组中间数的下标，break退出循环
23 break;
24 }
25 }
26 return -1;
27 }
28 int main()
29 {
30 int n; //数组的元素个数为 n
31 cout << "请输入数组的元素个数：" << endl;
32 cin >> n;
33 cout << "请输入数组：" << endl;
34 for (int i = 0; i < n; i++)
35 {
36 cin >> a[i]; //循环输入数组中的元素
37 }
38 cout << "请输入要查找的值：" << endl;
39 int target; //目标数
40 cin >> target;
41 cout << BinarySearch(a, target) << endl;
42
43 return 0;
44 }
关于代码中的middle = left + (right - left) / 2, ，不理解溢出的话，就死记住吧。
运行结果如下：
27. 移除元素
题目链接：https://leetcode.cn/problems/remove-element/
视频讲解：https://www.bilibili.com/video/BV12A4y1Z7LP
文章讲解：https://programmercarl.com/0027.%E7%A7%BB%E9%99%A4%E5%85%83%E7%B4%A0.html
卡哥的题目建议： 暴力的解法，可以锻炼一下我们的代码实现能力，建议先把暴力写法写一遍。 双指针法 是本题的精髓，今日需要掌握，至于拓展题目可以先不看。
有两种方法：暴力解法和双指针法。
暴力解法思路：用两个for循环，第一个for循环用来遍历数组，第二个for循环用来前移数据覆盖，就跟单链表的删除操作类似。完整代码如下：
1 #include <iostream>
2 using namespace std;
3 const int N = 10;
4 int a[N]; //声明全局数组
5 int main()
6 {
7 int n; //数组的元素个数为 n
8 cout << "请输入数组的元素个数：" << endl;
9 cin >> n;
10 cout << "请输入数组：" << endl;
11 for (int i = 0; i < n; i++)
12 {
13 cin >> a[i]; //循环输入数组中的元素
14 }
15 cout << "请输入要移除元素的值：" << endl;
16 int val;
17 cin >> val;
18 for (int i = 0; i < n; i++)//第一个循环是为了把遍历数组
19 {
20 if (a[i] == val) //判断数组的哪个数和要移除的数相等
21 {
22 for (int j = i; j < n; j++)//如果有一个数相等的话，那就从当前位置开始进行前移覆盖操作
23 {
24 a[j] = a[j + 1];//数组的后一个数前移覆盖当前位置的数
25 }
26 i--; //覆盖后，数组的有效元素减一，更新i值
27 n--; //数前移移除后，原来数组的有效元素减一，更新n值
28 }
29 }
30 cout << n << endl;
31 return 0;
32 }
运行结果如下：
双指针法做题思路：也称快慢指针法，通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。这个解法不用知道为啥，为了方便操作就行。
快指针：寻找新数组的元素 ，新数组就是不含有要移除的元素的数组；
慢指针：指向更新新数组下标的位置。
完整代码如下：
1 #include <iostream>
2 using namespace std;
3 const int N = 10;
4 int a[N]; //声明全局数组
5 int main()
6 {
7 int n; //数组的元素个数为 n
8 cout << "请输入数组的元素个数：" << endl;
9 cin >> n;
10 cout << "请输入数组：" << endl;
11 for (int i = 0; i < n; i++)
12 {
13 cin >> a[i]; //循环输入数组中的元素
14 }
15 cout << "请输入要移除元素的值：" << endl;
16 int val;
17 cin >> val;
18 int slow = 0; //慢指针的变量
19 for (int fast = 0; fast < n; fast++)
20 {
21 if (val != a[fast]) //如果fast位置上的元素和要移除的元素不相等的话，
22 {
23 a[slow] = a[fast]; //就把fast位置上的元素覆盖成slow位置上的元素
24 slow++;//slow虽然是下标，但是它也记录了新数组的个数，自己看视频就会发现
25 }
26 }
27 cout << slow << endl;
28 return 0;
29 }
运行结果如下：
标签：cout,int,元素,随想录,左闭,查找,数组,移除,LeetCode From： https://www.cnblogs.com/romantichuaner/p/17581700.html