LeetCode 刷题【34. 在排序数组中查找元素的第一个和最后一个位置、35. 搜索插入位置】

34. 在排序数组中查找元素的第一个和最后一个位置

自己做

解：二分查找

class Solution {
public:
    //二分查找
    int halfFind(vector<int> nums, int begin, int end, int target){
        if(begin > end)         //找不到的情况
            return -1;
        
        int mid = (begin + end) / 2;
        if(nums[mid] == target) //找到的情况
            return mid;
        
        if(nums[mid] > target)  //中轴偏大，往左边继续找
            return halfFind(nums, begin, mid - 1, target);

        if(nums[mid] < target)  //中轴偏小，往右边继续找
            return halfFind(nums, mid + 1, end, target);

        return 0;      //应付LeetCode
    }

    vector<int> searchRange(vector<int>& nums, int target) {
        //二分查找到元素
        int len = nums.size();

        if(len == 0)                //数组为空
            return {-1,-1};            

        int k = halfFind(nums, 0, len - 1, target);
        
        if(k == -1)                 //元素不存在
            return {-1,-1};
        
        //元素存在的情况
        int begin = k, end = k;
        //先往左边找
        while(begin >= 0 && nums[begin] == target)
            begin--;

        //再往右边找
        while(end < len && nums[end] == target)
            end++;

        return {begin + 1,end - 1};

    }
};

35. 搜索插入位置

自己做

解：二分查找

class Solution {
public:
    //二分查找
    int halfFind(vector<int> nums, int begin, int end, int target){
        if(begin > end)         //找不到的情况
            return end + 1;     //返回要插入的下标
        
        int mid = (begin + end) / 2;
        if(nums[mid] == target) //找到的情况
            return mid;
        
        if(nums[mid] > target)  //中轴偏大，往左边继续找
            return halfFind(nums, begin, mid - 1, target);

        if(nums[mid] < target)  //中轴偏小，往右边继续找
            return halfFind(nums, mid + 1, end, target);

        return 0;      //应付LeetCode
    }

    int searchInsert(vector<int>& nums, int target) {
        int len = nums.size();

        return halfFind(nums, 0, len - 1, target);
    }
};