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

���档讲解

数组理论，二分法，快慢指针

704.二分查找

思路：这道题一看到，第一时间肯定想得到一个for循环直接暴力，时间复杂度大概是O(n)，但分析一下题目的条件，如果用暴力求解，是不是有一个有序数组这个条件没用上，所以想到二分法！原理很简单，就是不断的取中点，然后判断要查找的目标是否中点左边还是右边。但是代码写起来还是有点问题的。

暴力求解:

class Solution {
public:
    int search(vector& nums, int target) {
        for(int i=0;i
            if(nums[i]==target)
            {
                return i;
            }
        }
        return -1;
    }
};

public:
    int bisearch(int begin,int end,vector
        if(begin==end||end-begin==1)
        {
            if(nums[begin]==target)return begin;
            else if(nums[end]==target)return end;
            else return -1;
        }
        int bipoint=(begin+end)/2;
        if(nums[bipoint]target)end=bipoint;
        else if(nums[bipoint]
        return bisearch(0,nums.size()-1,nums,target);
    }
};

public:
    int search(vector
        int begin=0;
        int end=nums.size()-1;
        while(begin
            int middle=begin+((end-begin)/2);
            if(nums[middle]
public:
    int search(vector
        int begin=0;
        int end=nums.size();
        while(begin
            int middle=begin+(end-begin)/2;
            if(nums[middle]
public:
    int removeElement(vector
        int slow=0;
        int fast=0;
        for(;fast
            if(nums[fast]==val){}
            else
            {
                nums[slow++]=nums[fast];
            }
        }
        return slow;
    }
};

        int l=0;
        int r=nums.size()-1;
        while(l
            int middle=l+(r-l)/2;
            if(nums[middle]
        int l=0;
        int r=nums.size()-1;
        while(l
            int middle=l+(r-l)/2;
            if(nums[middle]
        int start=getborder(nums,target);
        if(start==nums.size()||nums[start]!=target)
        return {-1,-1};
        int end=getborder(nums,target+1)-1;
        return{start,end};
    }

    int left = 0;
    int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    int rightBorder = -2; // 记录一下rightBorder没有被赋值的情况
    while (left  // 当left==right，区间[left, right]依然有效
        int middle = left + ((right - left) / 2);// 防止溢出 等同于(left + right)/2
        if (nums[middle]  target) {
            right = middle - 1; // target 在左区间，所以[left, middle - 1]
        } else { // 当nums[middle] == target的时候，更新left，这样才能得到target的右边界
            left = middle + 1;
            rightBorder = left;
        }
    }
    return rightBorder;
}

    int left = 0;
    int right = nums.size() - 1; // 定义target在左闭右闭的区间里，[left, right]
    int leftBorder = -2; // 记录一下leftBorder没有被赋值的情况
    while (left 
        int middle = left + ((right - left) / 2);
        if (nums[middle] = target) { // 寻找左边界，就要在nums[middle] == target的时候更新right
            right = middle - 1;
            leftBorder = right;
        } else {
            left = middle + 1;
        }
    }
    return leftBorder;
}