一. 簡介

本文記錄一下力扣網上涉及數組的問題：排序數組中查找目標值的位置。主要以C語言實現。

二.?力扣網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

題目分析：

首先，題目提到數組是非遞減序列，就是說從左到右元素是不嚴格遞增的，即每個元素大于或等于前一個元素。

其次，題目要求方法的時間復雜度必須是 ?O(log n)。

結合上面的信息可推測，本題目可能是要求使用二分查找法來實現。

1. 解題思路一（暴力解法）：

利用數組有序的特點從頭到尾遍歷一遍數組（相等的元素都在一起）。

暴力解法就是直接遍歷數組，找到 target第一次出現的位置和最后一次出現的位置。

這種解法的其實不滿足題目要求的，因為這種方法的時間復雜度是 O(n)，已經超過 O(log n)。

具體方法如下：

(1) 動態申請一段內存存放返回的數據（只要 存儲2個元素的緩存即可）；首先，緩存中元素都賦值為 -1；

(2) 遍歷數組，判斷 nums[i] 是否等于 target：

如果nums[i] 等于 target：再判斷 ret_ptr[0] 是否為初始值（確認是否是第一次出現的位置）；

ret_ptr[0] 是初始值：則記錄元素Index：ret_ptr[0] = index；ret_ptr[0] 不是初始值，則將當前的 index值更新到ret_ptr[1]：?ret_ptr[1] = index；

C語言實現如下：

//暴力解法
/*** Note: The returned array must be malloced, assume caller calls free().*/
int* searchRange(int* nums, int numsSize, int target, int* returnSize) {int i;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;for(i = 0; i < numsSize; i++) {if(nums[i] == target) {if(ret_ptr[0] == -1) { //判斷是否是第一次出現的位置,是則記錄下元素的indexret_ptr[0] = i;}ret_ptr[1] = i; //記錄最后一次出現的位置}}return ret_ptr;
}

這里實現上注意，當數組為空時，處理上返回了 申請的內存指針（但是這里內存也賦了初始值），而不是返回NULL。這樣做比較合適。

上面實現方法雖然編譯通過，但是該實現方法時間復雜度為 O(n)，不滿足題目要求。

下一篇文章使用二分查找法進行實現，因為二分查找法符合題目要求（時間復雜度為O(log n)）。