题目描述(Easy)
Given a sorted array of integers, find the starting and ending position of a given target value.
Your algorithm's runtime complexity must be in the order ofO(log n).
If the target is not found in the array, return[-1, -1].
题目链接
【牛客网】search-for-a-range
Note: leetcode原题地址找不到了，如果有找到请私信我。
Example 1:
Given[5, 7, 7, 8, 8, 10]and target value 8, return[3, 4].
算法分析
方法一：二分法+夹逼查找，最坏情况时间复杂度为；
方法二：二分法，先找到起始位，再找到末位。
提交代码：
class Solution { public: vector<int> searchRange(int A[], int n, int target) { int lower = lower_bound(A, 0, n, target); int upper = upper_bound(A, lower, n, target); if (lower == n || A[lower] != target) return vector<int>{-1, -1}; else return vector<int>{lower, upper - 1}; } private: int lower_bound(int A[], int first, int last, int target) { while (first < last) { int mid = (first + last) / 2; if (target > A[mid]) first = mid + 1; else last = mid; } return first; } int upper_bound(int A[], int first, int last, int target) { while (first < last) { int mid = (first + last) / 2; if (target >= A[mid]) first = mid + 1; else last = mid; } return first; } };
