2024/4/5-Force Button - 在排序数组中查找元素的第一个和最后一个位置

思路：二分法

方法一：分别查找左右侧边界

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int GetTargetFirstPosition(int *nums, int numsSize, int target) {
    int l = 0, r = numsSize - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        /* 找到 target，缩小搜索区间的上界 r ，不断向左收缩锁定左侧边界 */
        if (nums[mid] == target) {
            /* 在区间 [l, mid - 1] 中查找 */
            r = mid - 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else if (nums[mid] < target) {
            l = mid + 1;
        }
    }

    if (l == numsSize || nums[l] != target) {
        return -1;
    }
    return l;
}

int GetTargetLastPosition(int *nums, int numsSize, int target) {
    int l = 0, r = numsSize - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (nums[mid] == target) {
            l = mid + 1;
        } else if (nums[mid] > target) {
            r = mid - 1;
        } else if (nums[mid] < target) {
            l = mid + 1;   
        }
    }

    if (r == -1 || nums[r] != target) {
        return -1;
    }
    return r;
}

int* searchRange(int *nums, int numsSize, int target, int *returnSize) {
    int *res = malloc(sizeof(int) * 2);
    memset(res, -1, sizeof(res));
    *returnSize = 2;
    if (nums == NULL || numsSize < 1) {
        return res;
    }
    int firstPos = GetTargetFirstPosition(nums, numsSize, target);
    // 左边界没找到，右边界肯定也找不到
    if (firstPos == -1) {
        return res;
    }
    res[0] = firstPos;
    int lastPos = GetTargetLastPosition(nums, numsSize, target);
    res[1] = lastPos;
    return res;    
}

方法二：一次查找

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int binarySearch(int *nums, int numsSize, int target) {
    int l = 0, r = numsSize - 1;         
    while (l <= r) {            
        int mid = (l + r) >> 1;  
        if (nums[mid] == target) {            
            return mid;
        } else if (nums[mid] > target) {      
            r = mid - 1;
        } else if (nums[mid] < target) {      
            l = mid + 1;
        }
    }
    return -1;
}

int* searchRange(int *nums, int numsSize, int target, int *returnSize) {
    int *res = malloc(sizeof(int) * 2);
    memset(res, -1, sizeof(int) * 2);
    *returnSize = 2;
    if (nums == NULL || numsSize < 1) {
        return res;
    }
    int ind = binarySearch(nums, numsSize, target);
    if (ind == -1) {
        return res;
    }
    int i, j;
    for (i = ind - 1; i >= 0; i--) {
        if (nums[i] != target) {
            break;
        }
    }
    res[0] = i + 1;
    for (j = ind + 1; j < numsSize; j++) {
        if (nums[j] != target) {
            break;
        }
    }
    res[1] = --j;
    return res;
}