Readable C++11 solution


  • 8
    G
    class Solution {
    public:
        vector<int> searchRange(int A[], int n, int target) {
            vector<int> ans(2);
            ans[0] = lowerBound(A, A + n, target) - A;
            ans[1] = upperBound(A, A + n, target) - A - 1;
            if (ans[0] > ans[1]) {
                ans[0] = ans[1] = -1;
            }
            return ans;
        }
        
        int *lowerBound(int *a, int *b, int target)
        {
            return binarySearch(a, b, target, [](int a, int b) { return a < b; });
        }
        
        int *upperBound(int *a, int *b, int target)
        {
            return binarySearch(a, b, target, [](int a, int b) { return a <= b; });
        }
        
        int *binarySearch(int *a ,int *b, int target, function<bool(int, int) > cmp)
        {
            int l = 0, r = b - a;
            while (l < r) { 
                int mid = l + ((r - l) >> 1);
                if (cmp(a[mid], target)) {
                    l = mid + 1;
                } else {
                    r = mid;
                }
            }
            return a + l;
        }
    };

  • 0
    C

    why do you call it c++11?
    The compare function is cool!


  • 0
    G

    the compare function is anonymous function, this is new feature in C++11, you can see the article about it following this link http://en.wikipedia.org/wiki/C%2B%2B11


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.