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

题目：

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）已排序数组查找，二分查找

实现：

STL实现

 class Solution {

 public:

     vector<int> searchRange(int A[], int n, int target) {

        auto low_bound=lower_bound(A,A+n,target);//第一个大于等于>=target元素的指针位置

        auto up_bound=upper_bound(low_bound,A+n,target);//第一个大于>target元素的指针位置

        if(*low_bound==target)//target是否存在于A[]

        {

            return vector<int>{distance(A,low_bound),distance(A,prev(up_bound))};

        }

        else return vector<int>{-,-};

     }

 };

2. 常规实现

 class Solution {

 public:

     vector<int> searchRange(int A[], int n, int target) {

         int low=,high=n-,middle;

         bool isFind=false;

         vector<int> vec;

         while(low<=high)//二分查找，直至找到，并置标志true

         {

             middle=(low+high)/;

             if(A[middle]==target)

             {

                 isFind=true;

                 break;

             }

             else if(A[middle]<target)

                 low=middle+;

             else

                 high=middle-;

         }

         if(isFind)//如果找到，确定开始、结束与target相等的元素位置

         {

             low=middle;

             high=middle;

             while(low>=&&A[low]==target) low--;//下界要>=0

             low++;

             while(high<=n-&&A[high]==target) high++;//上界要<=n-1

             high--;

             vec.push_back(low);

             vec.push_back(high);

         }

         else//没有目标值

         {

             vec.push_back(-);

             vec.push_back(-);

         }

         return vec;

     }

 };

巴特西

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

最新文章

热门文章