力扣第三十四题——在排序数组中查找元素的第一个和最后一个位置

内容介绍

给你一个按照非递减顺序排列的整数数组 nums，和一个目标值 target。请你找出给定目标值在数组中的开始位置和结束位置。

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

你必须设计并实现时间复杂度为 O(log n) 的算法解决此问题。

示例 1：

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

示例 2：

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

示例 3：

输入：nums = [], target = 0
输出：[-1,-1]

提示：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109
• nums 是一个非递减数组
• -109 <= target <= 109

完整代码

 int binarySearch(int* nums, int numsSize, int target, bool lower) {int left = 0, right = numsSize - 1, ans = numsSize;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid;} else {left = mid + 1;}}return ans;
}int* searchRange(int* nums, int numsSize, int target, int* returnSize) {int leftIdx = binarySearch(nums, numsSize, target, true);int rightIdx = binarySearch(nums, numsSize, target, false) - 1;int* ret = malloc(sizeof(int) * 2);*returnSize = 2;if (leftIdx <= rightIdx && rightIdx < numsSize && nums[leftIdx] == target && nums[rightIdx] == target) {ret[0] = leftIdx, ret[1] = rightIdx;return ret;}ret[0] = -1, ret[1] = -1;return ret;
}

思路详解

代码概述

这段代码包含两个函数binarySearch和searchRange。binarySearch是一个改进的二分查找函数，用于查找目标值在数组中的位置，并根据一个布尔参数lower返回目标值的最小或最大索引。searchRange函数使用binarySearch来找到目标值在数组中的第一个和最后一个出现的位置。

binarySearch函数详解

binarySearch函数执行一个二分查找，并根据lower参数返回目标值的位置：

1. 初始化：

   • left和right分别初始化为数组的起始和结束索引。
   • ans初始化为数组的大小，作为未找到目标值时的默认返回值。

2. 二分查找循环：

   • 当left小于等于right时，计算中间位置mid。
   • 根据条件nums[mid] > target || (lower && nums[mid] >= target)来决定是向左还是向右移动指针：
     • 如果nums[mid]大于目标值，或者lower为真且nums[mid]大于等于目标值，则将右指针right移动到mid - 1，并将ans设置为mid。
     • 否则，将左指针left移动到mid + 1。

3. 返回结果：

   • 循环结束后，返回ans，它将是目标值在数组中的位置，或者如果目标值不存在，则为数组的大小。

searchRange函数详解

searchRange函数用于找到目标值在数组中出现的第一个和最后一个位置：

1. 查找目标值的左侧索引：

   • 调用binarySearch函数，传入true作为lower参数，以查找目标值的最小索引leftIdx。

2. 查找目标值的右侧索引：

   • 再次调用binarySearch函数，传入false作为lower参数，然后减1以获取目标值的最大索引rightIdx。

3. 检查结果的有效性：

   • 检查leftIdx是否小于等于rightIdx，且rightIdx小于数组大小，并且nums[leftIdx]和nums[rightIdx]是否都等于目标值。如果这些条件成立，说明目标值存在于数组中。

4. 分配和返回结果：

   • 使用malloc分配一个大小为2的整数数组ret来存储结果。
   • 如果目标值存在，将leftIdx和rightIdx存储在ret中。
   • 如果目标值不存在，将ret[0]和ret[1]都设置为-1。
   • 设置returnSize为2，表示返回数组的大小。
   • 返回ret。

代码注释

以下是代码中关键步骤的注释：

int binarySearch(int* nums, int numsSize, int target, bool lower) {int left = 0, right = numsSize - 1, ans = numsSize;while (left <= right) {int mid = (left + right) / 2;if (nums[mid] > target || (lower && nums[mid] >= target)) {right = mid - 1;ans = mid; // 更新答案为当前的mid} else {left = mid + 1;}}return ans; // 返回目标值的位置或数组大小
}int* searchRange(int* nums, int numsSize, int target, int* returnSize) {int leftIdx = binarySearch(nums, numsSize, target, true); // 查找左侧索引int rightIdx = binarySearch(nums, numsSize, target, false) - 1; // 查找右侧索引int* ret = malloc(sizeof(int) * 2); // 分配返回数组*returnSize = 2; // 设置返回数组的大小if (leftIdx <= rightIdx && rightIdx < numsSize && nums[leftIdx] == target && nums[rightIdx] == target) {ret[0] = leftIdx, ret[1] = rightIdx; // 如果目标值存在，则设置索引return ret;}ret[0] = -1, ret[1] = -1; // 如果目标值不存在，则返回{-1, -1}return ret;
}

知识点精炼

1. 二分查找算法（Binary Search）

• 基本概念：一种在有序数组中查找特定元素的搜索算法，通过不断将搜索区间减半来提高搜索效率。
• 时间复杂度：O(log n)，其中n是数组的长度。

2. 循环数组的处理

• 旋转数组：一个有序数组在某些点上被旋转，使得数组的一部分有序，另一部分同样有序，但整体不再有序。
• 二分查找的适应：通过比较中间元素与数组首元素，确定哪部分是有序的，从而决定搜索方向。

3. 边界条件处理

• 空数组：如果数组为空，直接返回-1，因为没有元素可以查找。
• 单元素数组：如果数组只有一个元素，直接比较该元素与目标值。

4. 循环与递归的选择

• 循环实现：使用while循环进行二分查找，避免了递归可能带来的额外开销。

5. 中间位置的取值

• 防止溢出：使用(left + right) / 2计算中间位置，而非(left + right) >> 1，虽然后者在位运算上更高效，但在此场景下避免了整型溢出的风险。

6. 搜索区间的调整

• 左半部分有序：如果中间元素大于等于首元素，说明左半部分是有序的，根据目标值的位置调整搜索区间。
• 右半部分有序：如果中间元素小于首元素，说明右半部分是有序的，同样根据目标值的位置调整搜索区间。

7. 返回结果

• 找到目标值：如果中间元素等于目标值，返回中间位置的索引。
• 未找到目标值：如果循环结束仍未找到目标值，返回数组的大小。

8. 算法优化

• 避免重复比较：在每次循环中，仅比较一次中间元素与目标值，减少了不必要的比较次数。

9. 动态内存分配

• 使用malloc：在searchRange函数中，使用malloc动态分配内存来存储结果数组。

10. 指针和数组的使用

• 指针传递：searchRange函数的返回值是一个指针，指向一个动态分配的数组。
• 数组访问：通过指针访问数组中的元素。

11. 函数返回值和指针

• 函数指针：searchRange函数的第二个参数是一个指向整数的指针，用于返回数组的大小。

通过以上知识点，我们可以看到，这段代码虽然简单，但涉及了二分查找算法、循环数组的处理、动态内存分配、指针和数组的使用等关键概念。这些知识点对于理解和实现高效的搜索算法至关重要