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

1、思路

因为是要找出给定目标值在数组中的开始位置和结束位置。

1. 所以开始位置的寻找，可以理解为在数组中寻找第一个满足条件的 $target$

2. 结束位置的寻找可以理解为在数组中寻找最后一个满足条件的 $target$

3. 至此就可以将题目简化成二分查找的特殊情况 （当 $l = r$）时找到。

   1. 在寻找第一个满足条件的 $target$ 的时候，满足 $target \le nums[mid]$ 时设置右边界 $r = mid$，这里不设置 $r = mid - 1$ 是因为 $r$ 可能就是第一个。
   2. 在寻找最后一个满足条件的 $target$ 的时候，满足 $target \ge nums[mid]$ 时设置右边界 $l = mid$，这里不设置 $l = mid + 1$ 是因为 $l$ 可能就是最后一个。

2、代码

int* searchRange(int* nums, int numsSize, int target, int* returnSize){
    int *ret = (int *)malloc(sizeof(int) * 2);
    ret[0] = -1;
    ret[1] = -1;
    *returnSize = 2;
    if (numsSize == 0) return ret;
    int l1 = 0, r1 = numsSize - 1;
    while (l1 != r1) {
        // 数组中寻找最后一个符合要求的target;
        int mid = l1 + (r1 - l1 + 1) / 2;
        if (target >= nums[mid]) l1 = mid;
        else r1 = mid - 1;
    }
    int l2 = 0, r2 = numsSize - 1;
    while (l2 != r2) {
        // 数组中寻找第一个符合要求的target;
        int mid = l2 + (r1 - l1) / 2;
        if (target <= nums[mid]) r2 = mid;
        else l2 = mid + 1; 
    }
    if (nums[l1] != target) return ret;
    ret[0] = l2;
    ret[1] = l1;
    return ret;
}