首页 > 代码库 > [Leetcode] search for a range 寻找范围

[Leetcode] search for a range 寻找范围

2024-10-21 19:17:39   208人阅读

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

 题意：找出目标值在给定序列中起始和终止下标值。

思路：这题关键的是对时间复杂度限制为O(logn)，所以，应该是二分查找算法的变形。刚开始，我还是想用一般的二分查找，找到等于目标值的下标了，然后向两边推进找到左右边界（此时，注意的下标）。但这种方法当重复的数字比较多的时，时间复杂度远不止O(logn)，见代码一。

方法二，分别用二分查找找到这个序列的左右边界，即可。这个方法中值得注意的是，选取边界条件时，if语句中的条件判断。见代码二：

代码一：

 1 class Solution {
 2 public:
 3     vector<int> searchRange(int A[], int n, int target) 
 4     {
 5         int lo=0,hi=n;
 6         while(lo<hi)
 7         {
 8             int mid=lo+(hi-lo)/2;
 9             if(A[mid]==target)
10                 break;
11             else if(target<A[mid])
12                 hi=mid;
13             else
14                 lo=mid+1;
15         }
16         if(A[mid] !=target)
17             return {-1,-1};
18 
19         lo=mid,hi=mid;
20         while(lo>=0&&A[lo]==target)
21             lo--;
22         while(hi<n&&A[hi]==target)
23             hi++;
24 
25         return {lo,hi};    
26     }
27 };

 

参考了Grandyang的博客，代码二：

 1 class Solution {
 2 public:
 3     vector<int> searchRange(int A[], int n, int target) 
 4     {
 5         vector<int> res(2,-1);
 6         int lo=0,hi=n;
 7 
 8         //找左边界
 9         while(lo<hi)
10         {
11             int mid=lo+(hi-lo)/2;
12             if(A[mid]<target)
13                 lo=mid+1;
14             else
15                 hi=mid;
16         }
17         if(A[hi] !=target)
18             return res;
19         
20         res[0]=hi;
21 
22         //右边界
23         hi=n;
24         while(lo<hi)
25         {
26             int mid=lo+(hi-lo)/2;
27             if(target<A[mid])
28                 hi=mid;
29             else
30                 lo=mid+1;
31         }
32         res[1]=lo-1;
33         return res;
34     }
35 };

 

[Leetcode] search for a range 寻找范围


联系
我们