Search for a Range-白红宇

Search for a Range

阅读量：2353 次

发布时间：2019-05-10

本文共 1165 字，大约阅读时间需要 3 分钟。

思路：

1、如果数组中不存在目标值，则返回[-1,-1]。

2、如果存在目标值，目标值索引为mid，上下范围为[i，j]，然后进入处理子程序。

3、两个子处理程序，分别在[i，mid]，[mid，j]中寻找目标值的边界。

题目：

Given an array of integers sorted in ascending order, 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:    int fun1(vector
    
     & nums, int low,int hi,int target) //寻找[i,mid]范围内的target边界    {        int i=low;        int j=hi;        int mid;        while(i<=j)        {            mid=(j-i)/2+i;            if(nums[mid]

& nums, int low,int hi,int target) //寻找[mid,j]范围内的target边界 { int i=low; int j=hi; int mid; while(i<=j) { mid=(j-i)/2+i; if(nums[mid]>target) j=mid-1; else i=mid+1; } return j; } vector

searchRange(vector

& nums, int target) { vector

res(2,-1); int len=nums.size(); if(len==0) return res; int i=0; int j=len-1; int mid; while(i<=j) { mid=(j-i)/2+i; if(nums[mid]

target) j=mid-1; else { res[0]=fun1(nums,i,mid,target); res[1]=fun2(nums,mid,j,target); return res; } } return res; }};