day1
二分查找
二分查找涉及很多的边界条件
while(left < right)
or
while(left <= right)
right = middle；
or
right = middle - 1；
区间的定义不同，边界处理方式不同
区间的定义一般为两种，左闭右闭[left, right]，
或者左闭右开[left, right)
左闭右闭
left=0;
right=numsize-1;
while(left<=right){
//
middle=（left-right）/2; // 因为区间是左闭右闭 左可以等于右边 所以left<=right是合法的
if(nums[middle]>target){
right=middle-1;
//nums[middle]>target 说明要搜索的值肯定不包括middle位置上的数，所以是middle-1；
}else if(nums[middle]<target){
left=middle+1;
}
}
左闭右开
left == right在区间[left, right)是没有意义的
所以 while (left < right)
left=numsize
//
if (nums[middle] > target) {
right = middle; //涉及到右边界改变时注意，因为是右开区间 如果取middle-1 则可能会漏掉目标值
} else if (nums[middle] < target) {
left = middle + 1;
} else { // nums[middle] == target
return middle;
}
class Solution{
public int serch(int[] nums,int target){
if(target<nums[0]||target>nums[nums.length-1]){
return -1;
}
int left=0,right=nums.length-1;
while(left<=right){
int mid=left+((right-left)>>1);
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
left=mid+1;
}else{
right=mid-1
}
return -1;
}
}
}
class Solution{
public int serch(int[] nums,int target){
if(target<nums[0]||target>nums[nums.length-1]){
return -1;
}
int left=0,right=nums.length;
while(left<right){
int mid=left+((right-left)>>1);
if(nums[mid]==target){
return mid;
}else if(nums[mid]<target){
left=mid+1;
}else{
right=mid;
}
return -1;
}
}
}
LeetCode：27. 移除元素
数组的元素在内存地址中是连续的，不能直接删除某个元素，只能通过覆盖的方式删除。
暴力解法 时间复杂度O（n^2）
class Solution {
public int removeElement(int[] nums, int val) {
int length=nums.length;
for(int i=0;i<nums.length;i++){
if(nums[i]==val){
for(int j=i;j<nums.length-1;j++){
nums[j]=nums[j+1];
}
length--;
i--; //注意不要忘记i-- 每删除一个元素之后 外层的遍历范围减一
}
}
return length;
}
}
双指针
快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组（筛选新元素）
慢指针：指向更新 新数组下标的位置（用来保存新元素）
class Solution {
public int removeElement(int[] nums, int val) {
int slow=0;
for(int fast=0;fast<nums.length;fast++){
if(nums[fast]!=val){ //不用删除的元素，则快慢指针一起向后遍历，如果遇到要删除的元素则快指针向后，慢指针不动，将元素覆盖。
nums[slow++]=nums[fast];
}
}
return slow;
}
}