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

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值 target，返回 [-1, -1]。

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

示例 2：

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109

 

思路：

变形二分，退出条件不在是找到就退出，而是找到边界
找左边界的时候尽量不要移动左边界
找右边界的时候尽量不要移动右边界

int Binary_Search(int *nums, int left, int right, int target, int flag){
    int ans = -1, rr = right;
    int mid ;
    while(left < right){
        mid = (left + right) / 2;
        if(nums[mid] == target)
            ans = mid;
        if(flag){//找右边界
            if(nums[right] == target)
                ans = right;
            //尽量不移动右边界
            if(nums[mid] > target)  
                right = mid  - 1;
            else
                left = mid + 1;
        }else{//找左边界，尽量不移动左边界
            if(nums[left] == target)
                  ans = left;
            if(nums[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
    }
    //加这个是为了防止下面的判断会非法访问内存，如访问nums[-1]和nums[numsSize]
    if(left < 0 || right < 0 || left > rr || right > rr )
            return ans;
    //防止left == right时是我们所求的边界
    if(nums[right] == target && flag)
        ans = right;
    else if(nums[left] == target)
        ans = left;
    return ans;
}
 
 
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    *returnSize = 2;
    int *ans = malloc(sizeof(int) * 2);
    ans[0] = ans[1] = -1;
    if(numsSize == 0)//剔除nums为空
        return ans;
    //找左边界
    ans[0] = Binary_Search(nums, 0, numsSize -1, target, 0);
    //找右边界
    ans[1] = Binary_Search(nums, 0, numsSize -1, target, 1);
    return ans;
}