力扣題目

給你一個(gè)按照非遞減順序排列的整數(shù)數(shù)組 nums，和一個(gè)目標(biāo)值 target。請(qǐng)你找出給定目標(biāo)值在數(shù)組中的開始位置和結(jié)束位置。

如果數(shù)組中不存在目標(biāo)值 target，返回 [-1, -1]。

你必須設(shè)計(jì)并實(shí)現(xiàn)時(shí)間復(fù)雜度為 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 是一個(gè)非遞減數(shù)組
-109 <= target <= 109

代碼

思路分析：使用兩次查找
1.第一次找到第一個(gè)target的位置；
2.第二次找到最后一個(gè)target的位置；
3.需要特別注意的是第一次查找找到target時(shí)，做的right = mid - 1;以及第二次查找找到target時(shí)，做的left = mid + 1;這兩次的操作特別重要。只有這樣才能找兩遍target的邊界值。代碼中也寫了詳細(xì)的注釋，希望大家認(rèn)真看一下。

int* searchRange(int* nums, int numsSize, int target, int* returnSize) 
{int first = -1, last = -1;int left = 0, right = numsSize - 1, mid = 0;int* arr = (int*)malloc(sizeof(int) * 2);/*查找一個(gè)等于target的位置*/while (left <= right){mid = left + (right - left) / 2;if (nums[mid] == target){first = mid;/*查看mid位置的左側(cè)是否還有等于target的值，確保first的的索引是第一個(gè)target的位置*/right = mid - 1;}else if (nums[mid] > target){right = mid - 1;}else{left = mid + 1;}}left = 0;right = numsSize - 1;/*查找最后一個(gè)等于target的位置*/while (left <= right){mid = left + (right - left) / 2;if (nums[mid] == target){last = mid;/*查看mid位置的右側(cè)是否還有等于target的值，確保last的的索引是最后一個(gè)target的位置*/left = mid + 1;}else if (nums[mid] > target){right = mid - 1;}else{left = mid + 1;}}*returnSize = 2;arr[0] = first;arr[1] = last;return arr;    
}