首页 > 其他 > 详细

leetcode 题解 || Search for a Range 问题

时间:2015-03-25 10:16:59      阅读:169      评论:0      收藏:0      [点我收藏+]

problem:

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

Hide Tags
 Array Binary Search
在一个已序数组中搜索一个数值的区间


thinking:


(1)又是对二分搜索的变形,我的策略是当遇到 A[mid] = target时,以mid为中心往两边探测,搜索区间范围。 


code:

class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
       
        if(n==0)
        {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        if(n==1)
        {
            if(A[0]==target)
            {
                res.push_back(0);
                res.push_back(0);
                return res;
            }
            else
            {
                res.push_back(-1);
                res.push_back(-1);
                return res;
            }
        }//if
        binary_search(A,0,n-1,target);
        return res;
    }
protected:
    void binary_search(int A[], int left, int right, int target)
    {
        if(left>right)
        {
            res.push_back(-1);
            res.push_back(-1);
            return;
        }
        int mid = (left+right)/2;
        if(A[mid]==target)
        {
           int i=mid,j=mid;
            while(i>=left && i<=right && A[i]==target)
                i--;
            res.push_back(++i);
            while(j>=left && j<=right &&A[j]==target)
                j++;
            res.push_back(--j);
            return;
        }
        else if(A[mid]>target)
            binary_search(A,left,mid-1,target);
        else
            binary_search(A,mid+1,right,target);
    }
private:
    vector<int> res;
     
        
    
};


leetcode 题解 || Search for a Range 问题

原文:http://blog.csdn.net/hustyangju/article/details/44617583

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!