首页 > 试题广场 >

求目标值的区间

[编程题]求目标值的区间
  • 热度指数:11942 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
给出一个有序数组,请在数组中找出目标值的起始位置和结束位置
你的算法的时间复杂度应该在O(log n)之内
如果数组中不存在目标,返回[-1, -1].
例如:
给出的数组是[50, 70, 70, 80, 80, 100],目标值是80,
返回[3, 4].
示例1

输入

[50, 70, 70, 80, 80, 100],80

输出

[3,4]
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) 
    {
     /// 方法1: 使用STL中的lower_bound,upper_bound或者equal_bound解决
     /*
     vector<int> res(2,-1);
     if(A==nullptr || n <=0)
       return res;
     int low = lower_bound(A,A+n,target)-A;
     if(low==n || A[low]!=target)
       return res;
     else res[0] = low;
    int high = upper_bound(A,A+n,target)-A-1;
    res[1] = high;
    return res; 
    */
   /// 方法2:使用二分查找,查找左右边界即可
  vector<int> res(2,-1);
  if(A==nullptr || n<=0)
    return res;
  int low = 0,high = n-1;
  while(low<=high)
  {
      int middle = (high+low)>>1;
      if(A[middle] < target)   /// 向左夹逼,则找到左边界
         low = middle+1;
      else
         high = middle-1;
  }

  int low2 = 0,high2 = n-1;
  while(low2 <=high2)
  {
      int middle2 = (high2+low2)>>1;
      if(A[middle2] <= target) /// 向右夹逼,找到右边界
         low2 = middle2+1;
      else
        high2 = middle2-1;
  }
  if(low <= high2)
  {
      res[0] = low;
      res[1] = high2;
  }
  return res;       
  }
};

编辑于 2017-07-12 10:42:43 回复(5)
public class Solution {
    public int[] searchRange(int[] A, int target) {
		int low = 0, high = A.length - 1, mid = 0;
		int start = - 1, end = - 1;
		while (low <= high) {
			mid = (low + high) / 2;
			if(A[mid] < target) low = mid + 1;
			else if(A[mid] > target) high = mid - 1;
			else {
				start = end = mid;
				while (start >= 0 && A[start] == target) start --;
				while (end < A.length && A[end] == target) end ++;
				return new int[] {start + 1, end - 1};
			}
		}
		return new int[] {start, end};
	}
}

发表于 2017-03-26 17:08:58 回复(7)
 
详细过程见我CSDN博客:https://blog.csdn.net/weixin_42047723/article/details/93721826 

我们先来看看时间复杂度为O(n)的算法,分别从左遍历和从右遍历数组,找到目标数的第一个下标位置分为是要求解的目标值的起始和结束位置

public class Solution {     public int[] searchRange(int[] A, int target) {         int res[] = new int[2];         res[0] = -1;         res[1] = -1;         //向左找         for(int i = 0 ; i < A.length; i++){             if(A[i] == target){                res[0] = i;                  break;             }         }        //向右找         for(int i = A.length - 1 ; i >= 0; i--){             if(A[i] == target){                res[1] = i;                  break;             }         }         return res;     } }
若要求时间复杂度为O(log n),我们可以利用二分查找的方法,该算法的时间复杂度为O(log n)。通过两次二分法查找,找到目标值的左边界和右边界,需要对二分查找法稍微加以修改。当查找右边界时,即当A[middle]小于等于目标数target时,low游标自增1继续往右走。同理当查找左边界时,即当A[middle]大于等于目标数target时,high游标自减1继续往左走。
public class Solution {     public int[] searchRange(int[] A, int target) {         int len = A.length;         int res[] = new int[2];         res[0] = -1;         res[1] = -1;         int low1 = 0, high1 = len - 1;         //查找右边界         while(low1 <= high1){             int middle1 = (low1 + high1) / 2;             if(A[middle1] <= target)                 low1 = middle1 + 1;             else                 high1 = middle1 - 1;         }         int low2 = 0, high2 = len - 1;         //查找左边界         while(low2 <= high2){             int middle2 = (low2 + high2) / 2;             if(A[middle2] >= target)                 high2 = middle2 - 1;             else                 low2 = middle2 + 1;         }         if(low2 <= high1){             res[0] = low2;             res[1] = high1;         }         return res;     } }

编辑于 2019-06-26 19:09:58 回复(1)
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
         int l=0,r=n-1,l2=0,r2=n-1;
         while(l<=r){
              int mid=l+(r-l)/2;
              if(A[mid]<target) l=mid+1;
              else r=mid-1;
         }
         while(l2<=r2){
              int mid=l2+(r2-l2)/2;
              if(A[mid]>target) r2=mid-1;
              else l2=mid+1;
         }
         vector<int> vec(2,-1);
         if(l<=r2)  vec[0]=l,vec[1]=r2;
         return vec;
    }
}; 


发表于 2017-08-04 10:20:53 回复(1)
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        auto pos1 =std::lower_bound(A, A+n, target);
        auto pos2 =std::upper_bound(A, A+n, target);
        if(*pos1 != target)
            return {-1,-1};
        return {int(pos1-A), int(pos2-A-1)};
    }
};

发表于 2017-03-13 14:52:44 回复(2)
题目要求 O(log n),找到目标值然后前后扫描,当遇到全部一样的数字不符合时间复杂度要求了。
发表于 2016-10-23 12:31:32 回复(1)
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        //时间复杂度为O(logn)
        int l=0,h=n,m;
        int start=-1,end=-1;
        while(l<h){
            m = l+((h-l)>>1);
            if(A[m]>target){
                h=m;
            }else if(A[m]<target){
                l=m+1;
            }else{//找到以后,需要确定前后边界
                int index = m;
                while(index>=0&&A[index]==target)index--;
                start = index+1;
                index=m;
                while(index<n&&A[index]==target)index++;
                end = index-1;
                break;
            }
        }
        vector<int> res;
        res.push_back(start);
        res.push_back(end);
        return res;
    }
};

发表于 2016-07-22 15:55:13 回复(1)
可以将left = 0;right = array.size()-1;
left++;right--;
每次比较与target的关系只要找到就可以不去自增或者自减了。
如果像个相交叉,就是没有找到,直接返回两个-1.
发表于 2016-07-26 22:51:25 回复(1)
讲真,B站这个解法是我看过讲的最清楚的一个了,还带有动画,非常好理解:https://www.bilibili.com/video/BV1wy4y1k76F?from=search&seid=4173688920308035659
想知道牛客提交之前是没有办法进行先编译测试的吗,直接就得提交?用LeetCode习惯了,但是又得知很多笔试题到时候还是在牛客做,所以还是回来这里也熟悉熟悉IDE
编辑于 2021-04-10 17:43:49 回复(0)
观点两次二分:
1.第一次二分找到第一个等于目标值
2.第二次二分找到最后一个等于目标值
class Solution {
public:
    /**
     *
     * @param A int整型一维数组
     * @param n int A数组长度
     * @param target int整型
     * @return int整型vector
     */
    vector<int> searchRange(int* A, int n, int target) {
        // write code here
        if (n<1)    return vector<int>{-1,-1};
        if (n==1){
            if (A[0]==target)
                return vector<int>{0,0};
            else
                return vector<int>{-1,-1};
        }
         
        vector<int> ans;
        int l=0,r=n-1;
        while (l<r){  //第一次二分找到第一个等于目标值
            int mid=(l+r)>>1;
            if (A[mid]>target)
                r=mid-1;
            else if (A[mid]<target)
                l=mid+1;
            else
                r=mid;
        }
        if (A[r]!=target)    return vector<int>{-1,-1};
        ans.push_back(r);
        l=r,r=n-1;
        while (l<r){//第二次二分找到最后一个等于目标值的
            int mid=(l+r+1)>>1;//此处加1的目的,让除法向上取整
            if (A[mid]>target)
                r=mid-1;
            else if (A[mid]<target)
                l=mid+1;
            else
                l=mid;
        }
        ans.push_back(l);
        return ans;
    }
};


发表于 2020-12-14 16:48:47 回复(0)
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        int l = 0;
        int r = n-1;
        vector<int> res;
        while(l <= r)
        {
            int mid = l + (r-l)/2;
            if(A[mid] == target)
            {
                if(A[l] == target && A[r] == target)
                {
                    res.push_back(l);
                    res.push_back(r);
                    return res;
                }
                if(A[l] != target)
                    ++l;
                if(A[r] != target)
                    --r;
            }
            else if(A[mid] < target)
                l = mid + 1;
            else
                r = mid-1;
        }
        return vector<int>(2,-1);
    }
};

发表于 2019-12-24 18:54:26 回复(0)
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        // 返回起始位置  有序数组
        vector<int> res(2,-1);
        int left = 0;
        int right = n - 1;
      
        int flag = 0;
        int mid;
        while(left <= right) 
        {
            mid = (right - left)/2 + left;
            if(A[mid] == target)
            {
                flag = 1;
                break;
            }
            else if(A[mid] < target)
                left = mid + 1;
            else
                right = mid - 1;
        }
        
        if( flag != 0)
        {
            int i = 1 , j  = 1;
            while(mid - i >= 0 && A[mid - i] == target) i++;
            while(mid + j < n && A[mid + j] == target) j++;
            res[0] = (mid - i + 1);
            res[1] = (mid + j - 1);
        }
        
        return res;
        
    }
};


发表于 2019-08-19 15:09:55 回复(0)
class Solution {
    public:
    // 一种新的思路,供大家参考
    // 改进二分查找,并通过修改target的值,使得最多经两次二分查找即可获得元素所在的区间
    // 复杂度O(logn) ~ O(2logn), 处于O(logn)级别,符合题目要求
    // 该算法最后的if-else判断应该还可以改进,如有好的想法请回复
    vector<int> searchRange(vector<int>& nums, int target) {
        if (nums.empty())
            return {-1, -1};
        int min_rank = -1, max_rank = -1;
        int lo = 0, hi = nums.size();
        while (lo < hi) { // 改进二分查找,使其总能返回多个命中元素的秩最大者。耗时O(logn)
            int mi = lo + ((hi - lo) >> 1);
            (target < nums[mi]) ? hi = mi : lo = mi + 1;
        } // 循环结束时,lo为大于target的元素的最小秩,故 --lo 即不大于target的元素的最大秩
        if (--lo != -1 && nums[lo] == target) { // 如target不存在可提前退出
            max_rank = lo; // 此时的lo即为target的最大秩(如存在)
            --target; hi = lo; lo = 0; // 第二次二分查找查找对象变为target - 1,查找区间缩小至[0, max_rank)
            while (lo < hi) { // 耗时O(log(max_rank + 1))
                int mi = lo + ((hi - lo) >> 1);
                (target < nums[mi]) ? hi = mi : lo = mi + 1;
            } // 循环结束时,lo为大于 target - 1 的元素的最小秩,即target的最小秩(如存在)
            min_rank = lo; // 此时的lo即为target的最小秩(如存在)
        }
        if (min_rank == -1)
            return {-1, -1};
        else
            return {min_rank, max_rank};
    }
};

发表于 2019-04-04 11:02:38 回复(0)
//二分法分别查找左右端点
public class Solution {
     public int[] searchRange(int[] A, int target) {
            int [] range = new int[2];
            range[0]= searchleft(A, target);
            range[1]= searchright(A, target);
            return range;
        }
    public int searchleft(int[] A, int target) {
        int low=0;
        int high= A.length-1;
        while (low<=high) {
            int mid=(low+high)>>1;
            if (target==A[mid]) {
                if (mid==0||A[mid-1]<target) {
                    return mid;
                }
                high=mid-1;
            }else if (target<A[mid]) {
                high=mid-1;
            }else {
                low=mid+1;
            }
        }
        return -1;
    }
    public int searchright(int[] A, int target) {
        int low=0;
        int high= A.length-1;
        while (low<=high) {
            int mid=(low+high)>>1;
            if (target==A[mid]) {
                if (mid==A.length-1||A[mid+1]>target) {
                    return mid;
                }
                low=mid+1;
            }else if (target<A[mid]) {
                high=mid-1;
            }else {
                low=mid+1;
            }
        }
        return -1;
    }
}
发表于 2018-06-21 15:53:31 回复(0)
public class Solution {
    public int[] searchRange(int[] A, int target) {
        int lo=0,hi=A.length-1;
        int left=-1,right=-1;
        while(lo<=hi){
            int mid=(hi-lo)/2+lo;
            if(target<A[mid]){
                hi=mid-1;
            }else if(target>A[mid]){
                lo=mid+1;
            }else{
                left=mid;
                right=mid;
                if(A[left]==target&&left-1>=lo&&A[left-1]==target){
                    int lo1=lo,hi1=mid-1;
                    while(lo1<=hi1){
                     int leftmid=(hi1-lo1)/2+lo1;
                        if(A[leftmid]<target){
                            lo1=leftmid+1;
                        }else if(A[leftmid]>target){
                            hi1=leftmid-1;
                        }else{
                            if(leftmid-1>=lo&&A[leftmid-1]==target){
                                hi1=leftmid-1;
                            }else{
                                left=leftmid;
                                break;
                            }
                        }
                    }
                }
                if(A[right]==target&&right+1<=hi&&A[right+1]==target){
                    int lo2=mid+1,hi2=hi;
                    while(lo2<=hi2){
                     int rightmid=(hi2-lo2)/2+lo2;
                        if(A[rightmid]<target){
                            lo2=rightmid+1;
                        }else if(A[rightmid]>target){
                            hi2=rightmid-1;
                        }else{
                            if(rightmid+1<=hi&&A[rightmid+1]==target){
                                lo2=rightmid+1;
                            }else{
                                right=rightmid;
                                break;
                            }
                        }
                    }
                }
                break;
            }
        }
        int[] result={left,right};
        return result;
    }
}

发表于 2018-04-03 11:30:06 回复(1)
/*
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].
*/
/*
思路:
使用二分查找法,
先找到一个target,然后分别向左和向右搜索target的边缘
*/
class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> v;

        v.push_back(-1);
        v.push_back(-1);

        int left = 0, right = n - 1;
        while (left <= right) {
            int mid = left + (right - left) / 2;
            if (nums[mid] == target) {
                theRes(nums, v, mid, target);

                return v;
            }
            else if (nums[mid] < target) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }

        return v;
    }

    void theRes(vector<int>& nums, vector<int>& v, int index, int target) {
        // 向左遍历
        int left = index;
        for (int i = index - 1; i >= 0; --i) {
            if (nums[i] == target) {
                left = i;
            }
            else {
                break;
            }
        }

        v[0] = left;

        int right = index;
        for (int i = index + 1; i < nums.size(); ++i) {
            if (nums[i] == target) {
                right = i;
            }
            else {
                break;
            }
        }

        v[1] = right;
    }
};
发表于 2017-12-04 10:26:04 回复(0)
  vector<int> searchRange(int A[], int n, int target) {
        vector<int> res;
        int low=0;
        int high=n-1;
        int mid;
        while(low<=high){
            mid=(low+high)/2;
            if(A[mid]==target){
                int i=mid;
                while(i-1>=0&&A[i]==A[i-1]) i--;
                int j=mid;
                while(j+1<=high&&A[j]==A[j+1]) j++;
                res.push_back(i);
                res.push_back(j);
                return res;
            }
            else if(A[mid]<target)
                low=mid+1;
            else
                high=mid-1;
        }
        res.push_back(-1);
        res.push_back(-1);
        return res;
        
    }

发表于 2017-11-06 21:35:15 回复(0)
class Solution {
public:
    vector<int> searchRange(int A[], int n, int target) {
        int l1=0,r1=n-1,l2=0,r2=n-1;
        while(l1 <= r1)
        {
        	int mid = l1+((r1-l1)>>1);
        	if(A[mid] < target)
        		l1 = mid + 1;
        	else
        		r1 = mid - 1;
		}
		while(l2 <= r2)
		{
			int mid = l2+((r2-l2)>>1);
			if(A[mid] > target)
				r2 = mid - 1;
			else
				l2 = mid + 1;
		}
		vector<int> result(2,-1);
		if(l1 <= r2)
		{
			result[0] = l1;
			result[1] = r2;
		}
		return result;
    }
};


发表于 2017-08-28 01:13:32 回复(0)
public class Solution {
    public int[] searchRange(int[] A, int target) {
        int[] a = {-1,-1};
		if(A==null||a.length<2)
			return a;
		int low, high, mid;
		low = 0;
		high = A.length - 1;

		while (low <= high) {
			mid = (high + low) / 2;
			if (target == A[mid]) {
				int temp = mid;
				//向前搜索
				while (mid - 1 >=0 && A[mid - 1] == target) {
					mid--;
				}
				a[0] = mid;
				mid = temp;
				//向后搜索
				while (mid + 1 < A.length && A[mid + 1] == target) {
					mid++;
				}
				a[1] = mid;
				break;
			} else if (target < A[mid]) {
				high = mid - 1;
			} else {
				low = mid + 1;
			}
		}
        return a;
    }
}

发表于 2016-06-02 14:40:52 回复(0)
import java.util.*;


public class Solution {
    /**
     * 
     * @param A int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] searchRange (int[] A, int target) {
        // write code here
                 if(A[0] > target || A[A.length-1] < target){             return new int[]{-1, -1};         }         int index = process(A, 0, A.length-1, target);         if(index == -1){             return new int[]{-1,-1};         }         return getRange(A, index);
    }
    
    private static int process(int[] arr, int l, int r, int target){         if(l == r){             return arr[l] == target ? l : -1;         }         int index = l+(r-l)/2;         if(arr[index] == target){             return index;         }         if(arr[index] > target){             return process(arr, l, index-1, target);         }else{             return process(arr, index+1, r, target);         }     }     private static int[] getRange(int[] arr, int index){         int l = index;         int r = index;         while(l > 0 && arr[l-1] == arr[index]){             l--;         }         while(r < arr.length-1 && arr[r+1] == arr[index]){             r++;         }         return new int[]{l, r};     }
}

编辑于 2022-02-08 21:08:37 回复(0)