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

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

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

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

代码一：

 class Solution {

 public:

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

     {

         int lo=,hi=n;

         while(lo<hi)

         {

             int mid=lo+(hi-lo)/;

             if(A[mid]==target)

                 break;

             else if(target<A[mid])

                 hi=mid;

             else

                 lo=mid+;

         }

         if(A[mid] !=target)

             return {-,-};

         lo=mid,hi=mid;

         while(lo>=&&A[lo]==target)

             lo--;

         while(hi<n&&A[hi]==target)

             hi++;

         return {lo,hi};

     }

 };

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

 class Solution {

 public:

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

     {

         vector<int> res(,-);

         int lo=,hi=n;

         //找左边界

         while(lo<hi)

         {

             int mid=lo+(hi-lo)/;

             if(A[mid]<target)

                 lo=mid+;

             else

                 hi=mid;

         }

         if(A[hi] !=target)

             return res;

         res[]=hi;

         //右边界

         hi=n;

         while(lo<hi)

         {

             int mid=lo+(hi-lo)/;

             if(target<A[mid])

                 hi=mid;

             else

                 lo=mid+;

         }

         res[]=lo-;

         return res;

     }

 };

巴特西

[Leetcode] search for a range 寻找范围

最新文章

热门文章