当前位置：首页 > news >正文

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

news 2024/11/5 2:37:53

力扣第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。具体思路如下：

查找第一个位置：通过二分查找找到 target 的第一个出现位置，即最左边的 target。
查找最后一个位置：同样使用二分查找找到 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 的第一个位置，使用二分查找实现。

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