C语言算法-解答在排序数组中查找元素的第一个和最后一个位置问题的C语言实现

题目

给定一个按照升序排序的整数数组 nums，和一个目标值 target，要求在数组中查找目标值的第一个和最后一个位置。如果目标值不存在于数组中，则返回 [-1, -1]。

引言

在排序数组中查找元素的第一个和最后一个位置问题需要考虑二分搜索和数组元素查找的逻辑。我们可以使用两次二分搜索的方法来解决这个问题，分别找到目标值的第一个位置和最后一个位置。解决这个问题需要进行两次二分搜索操作。

算法思路

我们将使用两次二分搜索的方法来解决在排序数组中查找元素的第一个和最后一个位置问题。

算法的步骤如下：

1. 定义两个变量 first 和 last，分别用于记录目标值的第一个位置和最后一个位置，初始值设为 -1。
2. 定义两个指针 left 和 right，分别指向数组的起始位置和结束位置。

3. 第一次二分搜索，查找目标值的第一个位置：

   • 计算 mid，即 left 和 right 的中间位置。
   • 如果 nums[mid] 大于等于目标值，说明目标值可能在左侧，将 right 更新为 mid-1。
   • 如果 nums[mid] 小于目标值，说明目标值可能在右侧，将 left 更新为 mid+1。
   • 如果 nums[mid] 等于目标值，将 mid 赋值给 first，然后继续向左侧查找更早的位置。

4. 第二次二分搜索，查找目标值的最后一个位置：

   • 将 left 重新设为数组的起始位置，将 right 设为数组的结束位置。
   • 同样的步骤进行二分搜索，不过这次找到目标值时，将 mid 赋值给 last，然后继续向右侧查找更晚的位置。
5. 返回 [first, last]，即目标值的第一个位置和最后一个位置。

代码实现

下面是使用C语言实现的代码：

#include <stdio.h>

int* searchRange(int* nums, int numsSize, int target, int* returnSize) {
    int* result = (int*)malloc(2 * sizeof(int));
    result[0] = -1;
    result[1] = -1;
    *returnSize = 2;

    int left = 0;
    int right = numsSize - 1;

    // 查找目标值的第一个位置
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] >= target) {
            right = mid - 1;
        } else {
            left = mid + 1;
        }
        if (nums[mid] == target) {
            result[0] = mid;
        }
    }

    // 查找目标值的最后一个位置
    left = 0;
    right = numsSize - 1;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        if (nums[mid] <= target) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
        if (nums[mid] == target) {
            result[1] = mid;
        }
    }

    return result;
}

int main() {
    int nums[] = {5, 7, 7, 8, 8, 10};
    int numsSize = sizeof(nums) / sizeof(nums[0]);
    int target = 8;
    int returnSize;

    int* result = searchRange(nums, numsSize, target, &returnSize);

    printf("Sorted Array: ");
    for (int i = 0; i < numsSize; i++) {
        printf("%d ", nums[i]);
    }
    printf("\n");

    printf("Target: %d\n", target);
    printf("Target's First and Last Positions: %d %d\n", result[0], result[1]);

    free(result);

    return 0;
}

算法分析

该算法进行了两次二分搜索，所以时间复杂度为 O(log n)，其中 n 是数组的长度。

空间复杂度为 O(1)，算法只使用了常数级别的额外空间。

示例和测试

示例输入:

Sorted Array: 5 7 7 8 8 10
Target: 8

示例输出:

Target's First and Last Positions: 3 4

总结

本文使用C语言实现了解答在排序数组中查找元素的第一个和最后一个位置问题的代码。通过使用两次二分搜索的方法，我们能够在给定的排序数组中查找目标值的第一个和最后一个位置。该算法的时间复杂度为 O(log n)，空间复杂度为 O(1)。