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

力扣第34题：在排序数组中查找元素的第一个和最后一个位置（C语言解法）

题目描述

在一个升序排列的整数数组 nums 中，找到指定元素 target 的第一个和最后一个位置。如果数组中不存在目标值 target，则返回 [-1, -1]。

示例 1：

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

示例 2：

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

要求：时间复杂度为 $O(\log n)$

解题思路

由于数组是升序排列的，因此可以使用二分查找来快速找到 target。具体思路如下：

1. 查找第一个位置：通过二分查找找到 target 的第一个出现位置，即最左边的 target。
2. 查找最后一个位置：同样使用二分查找找到 target 的最后一个出现位置，即最右边的 target。

这样两次二分查找就可以得到 target 的起始和结束位置。因为二分查找的时间复杂度为$O(\log n)$，所以整体复杂度也是$O(\log n)$。

代码实现

下面是具体的 C 语言实现。

#include <stdio.h>
#include <stdlib.h>

// 查找target的第一个位置
int findFirst(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    int first = -1;  // 初始化为-1，表示未找到
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            first = mid;       // 找到target，记录位置
            right = mid - 1;   // 向左缩小范围
        } else if (nums[mid] < target) {
            left = mid + 1;    // target在右侧
        } else {
            right = mid - 1;   // target在左侧
        }
    }
    return first;
}

// 查找target的最后一个位置
int findLast(int* nums, int numsSize, int target) {
    int left = 0, right = numsSize - 1;
    int last = -1;  // 初始化为-1，表示未找到
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] == target) {
            last = mid;        // 找到target，记录位置
            left = mid + 1;    // 向右缩小范围
        } else if (nums[mid] < target) {
            left = mid + 1;    // target在右侧
        } else {
            right = mid - 1;   // target在左侧
        }
    }
    return last;
}

// 主函数，返回target的起始和结束位置
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int* result = (int*)malloc(2 * sizeof(int));  // 分配返回结果的内存
    result[0] = findFirst(nums, numsSize, target);
    result[1] = findLast(nums, numsSize, target);
    *returnSize = 2;
    return result;
}

int main() {
    int nums[] = {5, 7, 7, 8, 8, 10};
    int target = 8;
    int returnSize;
    int* result = searchRange(nums, 6, target, &returnSize);
    printf("[%d, %d]\n", result[0], result[1]);  // 输出结果
    free(result);  // 释放内存
    return 0;
}

代码解析

函数 findFirst

findFirst 函数的作用是查找 target 的第一个位置，使用二分查找实现。

1. 初始化 left 和 right 为数组的左右边界。
2. 进入 while 循环，直到 left > right。
3. 计算 mid，这是当前的中间位置。
4. 如果 nums[mid] == target：
   • 记录 first = mid，表示找到了 target。
   • 将 right 设置为 mid - 1，继续向左查找，确保找到最左边的 target。
5. 如果 nums[mid] < target，说明 target 在右侧，将 left 更新为 mid + 1。
6. 如果 nums[mid] > target，说明 target 在左侧，将 right 更新为 mid - 1。
7. 最后返回 first，如果未找到 target 则返回 -1。

函数 findLast

findLast 函数的作用是查找 target 的最后一个位置，基本逻辑与 findFirst 类似：

1. 如果 nums[mid] == target，记录 last = mid，并将 left 设置为 mid + 1，继续向右查找。
2. 其他步骤与 findFirst 类似，最后返回 last。

主函数 searchRange

searchRange 使用 findFirst 和 findLast 得到 target 的起始和结束位置：

1. 动态分配 result 数组来存储结果，并调用 findFirst 和 findLast。
2. 将 returnSize 设置为 2，表示结果包含两个值。
3. 返回 result 数组。

时间复杂度

两个二分查找的时间复杂度都是$O(\log n)$，因此整体时间复杂度为$O(\log n)$，符合题目要求。