【Leetcode】Search for a Range

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 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 class Solution {
 2 public:
 3     vector<int> searchRange(int A[], int n, int target) {
 4         vector<int> ret(2, -1);
 5         int start = 0, end = n - 1;
 6         int mid;
 7         bool found = false;
 8         while (start <= end && !found) {
 9             mid = (start + end) / 2;
10             if (A[mid] == target) {
11                 found = true;
12             } else if (A[mid] < target) {
13                 start = mid + 1;
14             } else {
15                 end = mid - 1;
16             }
17         }
18         if (found) {
19             start = mid;
20             while (start - 1 >= 0 && A[start - 1] == target) {
21                 --start;
22             }
23             end = mid;
24             while (end + 1 < n && A[end + 1] == target) {
25                 ++end;
26             }
27             ret[0] = start;
28             ret[1] = end;
29         }
30         return ret;
31     }
32 };

View Code

二分查找。