给定一个已经升序排序的整形数组,找出给定目标值的开始位置和结束位置。
你的算法时间复杂度必须是 O(log n) 级别。
如果在数组中找不到目标,返回 [-1, -1]。
例如:
给出 [5, 7, 7, 8, 8, 10] 和目标值 8,
返回 [3, 4]。
详见:https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Java实现:
class Solution { public int[] searchRange(int[] nums, int target) { int n=nums.length; int[] result = { -1, -1 }; if(n==0||nums==null){ return result; } int left = 0; int right = n - 1; while (left <= right) { int mid = (left + right)>>1; if (nums[mid] > target) { right = mid - 1; } else if (nums[mid] < target) { left = mid + 1; } else { int index = mid; while (index >= 0 && nums[index] == target) { --index; } result[0]=index+1; index = mid; while (index < nums.length && nums[index] == target) { ++index; } result[1]=index-1; break; } } return result; } }
C++实现:
class Solution { public: vector<int> searchRange(vector<int>& nums, int target) { //时间复杂度为O(logn) int n = nums.size(); int l = 0, h = n-1, m; int start = -1, end = -1; while (l<=h) { m = l + ((h - l) >> 1); if (nums[m]>target) { h = m-1; } else if (nums[m]<target) { l = m + 1; } else {//找到以后,需要确定前后边界 int index = m; while (index >= 0 && nums[index] == target) { index--; } start = index + 1; index = m; while (index<n&&nums[index] == target) { index++; } end = index - 1; break; } } return vector<int>{start,end}; } };