Given an array of integers sorted in ascending order, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order of O(log n).
If the target is not found in the array, return [-1, -1].
For example,
Given[5, 7, 7, 8, 8, 10] and target value 8,return [3, 4]. 分析
思路1：
首先想到的思路是用二分法查找到target，然后从target开始，同时向左右两边扩展窗口，但是最坏的时间复杂度是O(n)；
思路2：
采用递归，recursive。
终止条件：
1. 当 nums[l] == target == nums[r]
返回{l,r}
2. 当 target 落在 [nums[l],nums[r]]之外，返回{-1,-1}
递归部分：
当 nums[l] <= target <= nums[r]， 分别对左半边和后半边进行search。同时将两个结果进行合并。
假设有一数组nums[]，我们把它分为两部分
A...B C...D
当出现终止条件中的一条时，都会立即返回；
如果俩个部分都进入了递归部分，说明
A <= target <= B
C <= target <= D
所以可以得知，
target = B = C
那么A..B的左边界就是nums的左边界，C..D的右边界就是nums的右边界，否则返回其中一个不是{-1,-1}的结果，就是这样合并两个结果的。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 | class Solution { public : vector< int > searchRange(vector< int >& nums, int target) { return helper(nums, 0, nums.size() - 1, target); } vector< int > helper(vector< int > & nums, int l, int r, int target){ if (nums.empty()) return vector< int >{-1,-1}; if (nums[l] == target && target == nums[r]){ return vector< int >{l,r}; } else if (nums[l] <= target && target <= nums[r]){ int mid = (l + r) >> 1; vector< int > L = helper(nums, l, mid, target); vector< int > R = helper(nums, mid+1, r, target); if (L[0] != -1 && R[0] != -1){ return vector< int > {L[0],R[1]}; } else if (L[0] != -1){ return L; } else { // 剩下的 R 不为{-1, -1} 和 R 是{-1, -1}的情况可以合并 return R; } } return vector< int >{-1, -1}; } }; |
思路3：
使用一般的二分查找，找到target的首个元素
然后再找 target+1 可以插入的首个位置，
这两者之间即为所求
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 | class Solution { public : vector< int > searchRange(vector< int >& nums, int target) { if (nums.empty()) return vector< int > {-1, -1}; int l = bs(nums, target); if (nums[l] == target){ int r = bs(nums, target + 1); /** * 当nums的最后一个元素是target的时候，需要将边界r自增才是可以插入target+1的位置 * 比如[2,2,2]则r的值是2，和[2,2,4]的返回值同是2, */ if (nums[r] == target) r++; return vector< int > {l, r - 1}; } else { return vector< int > {-1, -1}; } } // using binary search to find the first element in nums or the position that could be used to insert the element int bs(vector< int > & nums, int target){ int l = 0, r = nums.size() - 1, mid; while (l < r){ mid = (l + r) >> 1; if (nums[mid] < target){ l = mid + 1; } else { r = mid; } } return r; } }; |
思路4
写两个找边界的函数，一个找上边界，一个找下边界；
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 | class Solution { public : vector< int > searchRange(vector< int >& nums, int target) { if (nums.empty()) return vector< int > {-1, -1}; int l = lob(nums, target); if (nums[l] == target){ int r = upb(nums, target); return vector< int > {l, r}; } return vector< int > {-1, -1}; } int lob(vector< int > & nums, int target){ int l = 0, r = nums.size() - 1, mid; while (l < r){ mid = (l + r) >> 1; // insure the mid always be at the lower position if (nums[mid] < target){ l = mid + 1; } else { r = mid; } } return r; } int upb(vector< int > & nums, int target){ int l = 0, r = nums.size() - 1, mid; while (l < r){ mid = (l + r + 1) >> 1; // insure the mid always be at the upper position if (nums[mid] > target){ r = mid - 1; } else { l = mid; } } return l; } }; |