LeetCode Search for a Range

class Solution {
private:
    int getDirection(int A[], int idx, int target, bool isDefaultBack) {
        int r = A[idx] - target;
        if (r == 0) {
            r = isDefaultBack ? -1 : 1;
        }
        return r;
    }   
    int getFirstValueIndex(int A[], int n, int target, bool isFromBack) {
        int p = -1; 
        int q = n;
        while (p + 1 < q) {
            int mid_idx = (p + q) / 2;
            int where = getDirection(A, mid_idx, target, isFromBack);
            if (where < 0) {
                p = mid_idx;
            } else {
                q = mid_idx;
            }
        }
        if (p != -1 && A[p] != target) {
            p = -1; 
        }
        if (q == n || A[q] != target) {
            q = -1; 
        }
        return isFromBack ? p : q;
    }   
public:
    vector<int> searchRange(int A[], int n, int target) {
        vector<int> res;
        res.push_back(getFirstValueIndex(A, n, target, false));
        res.push_back(getFirstValueIndex(A, n, target, true));
        return res;
    }   
};

进行两次二分查找，一次找upper bound一次找lower bound，如果线性查找的化就不符合要求了。

第二轮：

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> res(2, -1);
 5         if (A == NULL || n < 1 || target < A[0] || target > A[n-1]) {
 6             return res;
 7         }
 8         
 9         int lo = 0, hi = n-1;
10         
11         int st = lower_bound(A, A + n, target) - A;
12         if (st >= n || A[st] != target) {
13             return res;
14         } 
15         int ed = upper_bound(A, A + n, target) - A;
16         res[0] = st;
17         res[1] = ed-1;
18         return res;
19     }
20 };

如果自己写lower_bound和upper_bound的话：

 1 class Solution {
 2 public:
 3     vector<int> searchRange(int A[], int n, int target) {
 4         vector<int> res(2, -1);
 5         if (A == NULL || n < 1 || target < A[0] || target > A[n-1]) {
 6             return res;
 7         }
 8         
 9         int lo = 0, hi = n;
10         // lower_bound
11         while (lo < hi) {
12             int mid = (lo + hi) / 2;
13             if (A[mid] < target) {
14                 lo = mid + 1;
15             } else {
16                 hi = mid;
17             }
18         }
19         
20         if (A[lo] != target) {
21             return res;
22         }
23         res[0] = lo;
24         
25         lo = 0, hi = n;
26         // upper_bound
27         while (lo < hi) {
28             int mid = (lo + hi) / 2;
29             if (A[mid] <= target) {
30                 lo = mid + 1;
31             } else {
32                 hi = mid;
33             }
34         }
35         res[1] = lo - 1;
36 
37         return res;
38     }
39 };