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 的左边界第二次二分找到 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]八、总结本题的关键在于二分查找边界问题。查找类型判断条件左边界nums[mid] target右边界nums[mid] target记忆口诀找左边界 找右边界通过两次二分查找即可在O(log n)时间内解决问题。