LeetCode: Search for a Range

题目

https://oj.leetcode.com/problems/search-for-a-range/

分析

时间复杂度O(log n), 多半便是二分查找的题目。

题目要求找出一个范围,无非就是找到一个起始点和一个终止点,通过两次二分查找找到起始点和终止点即可。

起始点的特点是,等于target,而且它左侧没有target了或者它是数组第一个数。

终止点的特点是,等于target,而且它右侧没有target了或者它是数组最后一个数。

P.S. 标准二分查找代码可以查看这里

代码

class Solution
{
public:
    vector<int> searchRange(int A[], int n, int target)
    {
        vector<int> res;
        int l, r, m;

        l = 0;
        r = n - 1;
        while (l <= r)
        {
            m = (l + r) >> 1;
            if ((A[m]==target) && (m==0 || A[m-1]!=target))
            {
                res.push_back(m);
                break;
            }
            else if (A[m] > target || A[m-1] == target)
                r = m - 1;
            else
                l = m + 1;
        }
        if (res.size() == 0)
        {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }

        l = 0;
        r = n - 1;
        while (l <= r)
        {
            m = (l + r) >> 1;
            if ((A[m]==target) && (m==n-1 || A[m+1]!=target))
            {
                res.push_back(m);
                break;
            }
            else if (A[m] < target || A[m+1] == target)
                l = m + 1;
            else 
                r = m - 1;
        }
        return res;
    }
};

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40477301