首页 > 代码库 > leetcode题解:Search for a Range (已排序数组范围查找)

leetcode题解:Search for a Range (已排序数组范围查找)

2024-07-11 15:21:01   217人阅读

  • 题目：

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

  • 说明：

              1）已排序数组查找，二分查找

  • 实现：
  1. STL实现
 1 class Solution { 2 public: 3     vector<int> searchRange(int A[], int n, int target) { 4        auto low_bound=lower_bound(A,A+n,target);//第一个大于等于>=target元素的指针位置 5        auto up_bound=upper_bound(low_bound,A+n,target);//第一个大于>target元素的指针位置 6        if(*low_bound==target)//target是否存在于A[] 7        { 8            return vector<int>{distance(A,low_bound),distance(A,prev(up_bound))}; 9        }10        else return vector<int>{-1,-1};11         12     }13 };

     2.  常规实现

 1 class Solution { 2 public: 3     vector<int> searchRange(int A[], int n, int target) { 4         int low=0,high=n-1,middle; 5         bool isFind=false; 6         vector<int> vec; 7         while(low<=high)//二分查找，直至找到，并置标志true 8         { 9             middle=(low+high)/2;10             if(A[middle]==target) 11             {12                 isFind=true;13                 break;14             }15             else if(A[middle]<target)16                 low=middle+1;17             else18                 high=middle-1;19         }20         if(isFind)//如果找到，确定开始、结束与target相等的元素位置21         {22             low=middle;23             high=middle;24             while(low>=0&&A[low]==target) low--;//下界要>=025             low++;26             while(high<=n-1&&A[high]==target) high++;//上界要<=n-127             high--;28             vec.push_back(low);29             vec.push_back(high);30         }31         else//没有目标值32         {33             vec.push_back(-1);34             vec.push_back(-1);35         }36         return vec;37     }38 };

 


联系
我们