LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置（C语言 | 二分查找）

一、题目描述

给你一个按照非递减顺序排列的整数数组nums，和一个目标值target。

请你找出给定目标值在数组中的开始位置和结束位置。

如果数组中不存在目标值target，返回[-1,-1]。

要求算法时间复杂度必须为：

O(log n)

示例：

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

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

二、解题思路

由于数组是有序数组，并且要求时间复杂度O(log n)，因此可以想到使用二分查找。

但本题需要找到：

target 的最左位置 target 的最右位置

因此我们需要进行两次二分查找：

三、寻找左边界

目标：

找到第一个 >= target 的位置

二分逻辑：

nums[mid] >= target r = mid - 1 else l = mid + 1

循环结束后：

l 就是第一个 >= target 的位置

再判断：

nums[l] == target

否则说明不存在。

四、寻找右边界

目标：

找到最后一个 <= target 的位置

二分逻辑：

nums[mid] <= target l = mid + 1 else r = mid - 1

循环结束后：

r 就是最后一个 <= target 的位置

五、算法流程

完整步骤：

1. 二分查找 target 的左边界 2. 如果不存在 target，返回 [-1,-1] 3. 二分查找 target 的右边界 4. 返回结果

时间复杂度：

O(log n)

空间复杂度：

O(1)

六、C语言实现

/** * Note: The returned array must be malloced, assume caller calls free(). */ int* searchRange(int* nums, int numsSize, int target, int* returnSize) { int* res = (int*)malloc(sizeof(int) * 2); *returnSize = 2; res[0] = -1; res[1] = -1; if (numsSize == 0) return res; int l = 0; int r = numsSize - 1; // 查找左边界 while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] >= target) r = mid - 1; else l = mid + 1; } if (l >= numsSize || nums[l] != target) return res; res[0] = l; // 查找右边界 r = numsSize - 1; while (l <= r) { int mid = l + (r - l) / 2; if (nums[mid] <= target) l = mid + 1; else r = mid - 1; } res[1] = r; return res; }

七、示例分析

输入：

nums = [5,7,7,8,8,10] target = 8

查找左边界：

最终 l = 3

查找右边界：

最终 r = 4

返回：

[3,4]

八、总结

本题的关键在于二分查找边界问题。

记忆口诀：

找左边界：>= 找右边界：<=

通过两次二分查找即可在O(log n)时间内解决问题。