[leetcode] 34. Search for a Range

作者:luozhipeng   发表日期:2016-8-21  浏览:623次

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

 

题意:给出一个有序数组和一个目标数target,求返回target的在数组中的开始和结束的索引,如果数组中没有target,则返回[-1,-1]

 

思路:使用两次二分查找找到target的左右边界。

 

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int len = nums.size();
        int left = 0, right = len - 1;
        vector<int> ans = {-1, - 1};
        while(left <= right)
        {
            int mid = left + (right - left)/2;
            if(nums[mid] >= target)
                right = mid - 1;
            else
                left = mid + 1;
        }
        ans[0] = left;
        
        right = len - 1;
        while(left <= right)
        {
            int mid = left + (right - left)/2;
            if(nums[mid] <= target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        ans[1] = right;
        if(nums[ans[0]] == target && nums[ans[1]] == target)
            return ans;
        return {-1,-1};
    }
};

本文固定链接: http://www.luozhipeng.com/?p=1096
转载请注明: luozhipeng 2016-8-21 于 罗志鹏的BLOG 发表

上一篇: :下一篇
评论:请安装多说插件!
返回顶部