一. 简介
上一篇文章对力扣网上"有序数组中查找目标值范围"题目进行了普通的解法。文章如下：
力扣网C语言编程题：在数组中查找目标值位置之暴力解法-CSDN博客
本文使用二分查找法进行实现，因为二分查找法符合题目要求（时间复杂度为 O(log n)）。
二. 力扣网C语言编程题：在数组中查找目标值位置之二分查找法
题目：在排序数组中查找元素的第一个和最后一个位置
给你一个按照非递减顺序排列的整数数组 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
1. 解题思路二：（二分查找法）
题目说数组是非递减序列，也就是说数组元素从左到右元素是不严格递增的，即每个元素大于或等于前一个元素。有序序列中查找一个目标值，符合 "二分查找法" 的特点。
首先，查找target 第一次出现的位置，并记录下来；
其次，查找target最后一次出现的位置，并记录下来；
C语言实现如下：
//二分查找法
int* searchRange(int* nums, int numsSize, int target, int* returnSize){
int* ret_ptr = (int*)malloc(2*sizeof(int));
ret_ptr[0] = -1;
ret_ptr[1] = -1;
if((nums == NULL) || (numsSize <= 0) || (returnSize == NULL)) {
return ret_ptr;
}
*returnSize = 2;
//查找第一次出现的位置
int left = 0;
int right = numsSize-1;
int mid = 0;
while(left <= right) {
mid = (left+right) / 2;
if(nums[mid] >= target) {//向左收缩区间
right = mid - 1;
}
else { //nums[mid] < target, 向右收缩区间
left = mid + 1;
}
}
//需要额外判断是否真的找到了target
if((left < numsSize) && (nums[left] == target)) {
ret_ptr[0] = left;
}
else{
return ret_ptr;
}
//查找最后一次出现的位置
right = numsSize-1;
while(left <= right) {
mid = (left + right) / 2;
if(nums[mid] <= target) {//向右收缩区间
left = mid + 1;
}
else {//nums[mid] > target,向左收缩区间
right = mid - 1;
}
}
ret_ptr[1] = right;
return ret_ptr;
}(1) 查找目标值 target 第一次出现的位置的实现思路?
目标：
找到第一个等于 target 的索引。换句话说，我们要找到最小的下标 i，使得 nums[i] == target。
理解逻辑的关键点
注意: 这段二分查找不是寻找 “等于”，而是不断缩小范围，直到 left 指向第一个满足条件的元素。
思路拆解：
我们始终维护一个区间 [left, right]，表示目标值可能在这个区间内。
如果 nums[mid] < target：说明要找的目标在右边，于是 left = mid + 1
如果 nums[mid] >= target：说明目标可能在左边或当前位置，于是 right = mid - 1
注意：即使 nums[mid] == target，我们也继续往左找，看看有没有更早的相同值。
循环结束时的状态：
当 while (left <= right) 跳出循环时，right < left，此时 left 是第一个大于等于 target 的位置。
如果 target 存在于数组中，那么 left 正好指向它第一次出现的位置。
(2) 查找目标值 target 最后一次出现的位置的实现思路?
目标：
我们要找到 最后一个等于 target 的位置。换句话说，我们要找到最大的下标 i，使得 nums[i] == target。
核心思想：
我们仍然使用二分查找，但这次不是找第一个大于等于 target 的位置，而是：
如果 nums[mid] <= target，说明可能还有更大的、也等于 target 的位置在右边 → 向右缩
如果 nums[mid] > target，说明当前点和右边都太大了 → 向左缩
思路拆解：
我们始终维护一个区间 [left, right]，表示目标值可能在这个区间内。
当 nums[mid] <= target 时，我们尝试往右找是否有更靠后的相同值。
即使 nums[mid] == target，我们也继续向右搜索，看有没有更多相同的值。
这样，随着循环不断进行，left 最终会停在 最后一个 target 的下一个位置，所以最终的位置是 right。
循环结束时的状态：
当 while (left <= right) 跳出循环时，left > right，此时：
right 是最后一个 ≤ target 的位置。
如果 nums[right] == target，那它就是最后一次出现的位置。
三. 总结：
问题 |
回答 |
为什么跳出循环后 left 是第一个 target 出现的位置？ |
因为我们使用的是 “左缩” 策略，最终 left 停在第一个 ≥ target 的位置，如果存在 target，那这个位置就是它的首次出现。 |
为什么跳出循环后 right 是最后一个 target 出现的位置？ |
因为我们使用的是 “右缩” 策略，最终 right 停在最后一个 ≤ target 的位置，如果存在 target，那这个位置就是它的最后一次出现。 |
时间复杂度是多少？ |
O(log n) |