【Search for a Range】cpp

题目：

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].

代码：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> ret;
            int pos = Solution::findPos(nums, target, 0, nums.size()-1);
            if ( pos==-1 )
            {
                ret.push_back(-1);
                ret.push_back(-1);
                return ret;
            }
            int l = Solution::findLeft(nums, target, 0, pos);
            ret.push_back(l);
            int r = Solution::findRight(nums, target, pos+1, nums.size()-1);
            ret.push_back(r);
            return ret;
    }
            static int findPos(vector<int>& nums, int target, int begin, int end)
        {
            if ( begin>end ) return -1;
            int mid = (begin+end)/2;
            if ( nums[mid]==target ) return mid;
            if ( nums[mid]>target )
            {
                return Solution::findPos(nums, target,begin,mid-1);
            }
            else
            {
                return Solution::findPos(nums, target, mid+1, end);
            }
        }
        static int findLeft(vector<int>& nums, int target, int begin, int end)
        {
            if ( begin>end ) return begin;
            int mid = (begin+end)/2;
            if ( nums[mid]<target )
            {
                return Solution::findLeft(nums, target, mid+1, end);
            }
            else
            {
                return Solution::findLeft(nums, target, begin, mid-1);
            }
        }
        static int findRight(vector<int>& nums, int target, int begin, int end)
        {
            if ( begin>end ) return end;
            int mid = (begin+end)/2;
            if ( nums[mid]>target )
            {
                return Solution::findRight(nums, target, begin, mid-1);
            }
            else
            {
                return Solution::findRight(nums, target, mid+1, end);
            }
        }
};

tips：

按照常规的思路写的。

1. 首先二分查找target变量的某个位置，如果没有则直接返回-1

2. 确定有target变量了，则分左右两边找

　　1）左侧：找最左边的target的元素

　　2）右侧：找最右边的target元素

注意处理好边界的case。

=================================

学习了一种STL的写法 代码如下：

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> ret;
            const int l = std::distance(nums.begin(), std::lower_bound(nums.begin(), nums.end(), target));
            const int u = std::distance(nums.begin(), std::upper_bound(nums.begin(), nums.end(), target));if (nums[l]!=target)
            {
                ret.push_back(-1);
                ret.push_back(-1);
            }
            else
            {
                ret.push_back(l);
                ret.push_back(u>0?u-1:0);
            }
            return ret;
    }
};

非常简洁。

不知道为什么，在mac的sublime上coding时，prev() next() 这俩函数一直不让用。

=============================================

第二次过这道题，就是用二分查找的思路。找左边界，右边界。代码比第一次过的时候简洁一些。

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
            vector<int> ret;
            int l = -1;
            int r = -1;
            int begin = 0;
            int end = nums.size()-1;
            // search for left bound
            while ( begin<=end )
            {
                int mid = (begin+end)/2;
                if ( nums[mid]==target )
                {
                    l = mid;
                    end = mid-1;
                }
                else if ( nums[mid]>target )
                {
                    end = mid-1;
                }
                else
                {
                    begin = mid+1;
                }
            }
            if ( l==-1 ) { ret.push_back(l); ret.push_back(r); return ret; }
            // search for right bound
            begin = l;
            end = nums.size()-1;
            while ( begin<=end )
            {
                int mid = (begin+end)/2;
                if ( nums[mid]==target )
                {
                    r = mid;
                    begin = mid+1;
                }
                else
                {
                    end = mid-1;
                }
            }
            ret.push_back(l);
            ret.push_back(r);
            return ret;
    }
};