力扣704. 二分查找
思路：假如有n个数，数组下标就是0到n-1，那么第一次从n/2开始找
如果这个数比目标数大，说明目标数在左边，于是从0到中间边界找。
如果这个数比目标数小，说明目标数在右边，于是从中间边界+1到n-1找。
为了明确中间边界是多少，举个例子：
假如数组是：0,1,3,5,6,7,8; target = 7;
假如target=1呢，第一次还是从下标3开始找，也就是5开始，发现5比目标数1大，那么从0到5的上一位开始找。
上面是数组长度为奇数的情况那么如果长度为偶数呢？
比如数组是：0,1,3,5,6,7,8,9; target = 8
数组大小是8， 从4开始找，找到6，发现8比6大，于是从下一位到末尾查找。
由此可以发现，这和数组大小的奇偶性质没有关系。
于是可得逻辑
if (nums[cur] > target)
{
right = cur - 1;
}
if (nums[cur] < target)
{
left = cur + 1;
}
接下来写代码
class Solution {
public:
int search(vector<int>& nums, int target) {
//左下标
int left = 0;
//右下标
int right = nums.size() - 1;
//中间下标
int cur;
while(left < right)
{
cur = (left + right) / 2;
if (nums[cur] == target)
{
return cur;
}
else if (nums[cur] > target)
{
right = cur - 1;
}
else
{
left = cur + 1;
}
}
return -1;
}
};
代码逻辑比较简单，提交！
OH, No!
没有ac，提示用例是只有一个数的数组。
为什么没通过，思考一下如果只有两个数的数组0, 1，目标值是1
根据代码逻辑，开始值查找的是0，不是目标值，下一个left为1，此时right也是1，循环结束。
因此应该把while循环的条件改为小于等于
class Solution {
public:
int search(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
int cur;
while(left <= right)
{
cur = (left + right) / 2;
if (nums[cur] == target)
{
return cur;
}
else if (nums[cur] > target)
{
right = cur - 1;
}
else
{
left = cur + 1;
}
}
return -1;
}
};
成功ac！
此题除了改动while循环条件，也可以一开始就将right设置为nums.size()，这样相当于用于比真实的下标大1，此时while循环条件就可以填小于。
因此第一种解法，称之为左闭右闭区间，第二种解法称之为左闭右开区间！
力扣27. 移除元素
思路：快慢指针，一个快指针负责遍历数组，如果找到数值不是val的数，那么把数值赋值给慢指针，然后慢指针移动到下一位。
其实这个思路就是一个萝卜一个坑，快指针负责出去找萝卜，慢指针在家里等着，有萝卜了就把萝卜放进去，然后去下一个坑等着
代码实现：
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int j = 0;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] != val)
{
nums[j] = nums[i];
j++;
}
}
return j;
}
};
总结
明天面试，这两个等有时间刷。35.搜索插入位置 和 34. 在排序数组中查找元素的第一个和最后一个位置