（算法）二分查找的搜索区间-白红宇

（算法）二分查找的搜索区间

阅读量：7052 次

发布时间：2019-06-28

本文共 1076 字，大约阅读时间需要 3 分钟。

题目：

给定一个包含 n 个整数的排序数组，找出给定目标值 target 的起始和结束位置。

如果目标值不在数组中，则返回[-1, -1]

思路：

1、直接遍历数组，复杂度O(n)

2、二分查找

先通过二分查找，找到target出现的最左边的位置，如果不存在，返回-1；

再通过二分查找，找到target出现的最右边的位置，如果不存在，返回-1；

代码：

#include
     
      #include
      
       using namespace std;int searchLeft(const vector
       
         &A,int left,int right,int target){    int first=left;    int last=right;    int mid=-1;    while(first<=last){        mid=first+((last-first)>>1);        if(A[mid]==target){            if(mid>left && A[mid-1]==target)                last=mid-1;            else                return mid;        }        else if(A[mid]

&A,int left,int right,int target){ int first=left; int last=right; int mid=-1; while(first<=last){ mid=first+((last-first)>>1); if(A[mid]==target){ if(mid

&A,int left,int right,int target,int &start,int &end){ start=searchLeft(A,left,right,target); end=searchRight(A,left,right,target);}int main(){ int n; int start=-1; int end=-1; int target; while(cin>>n){ vector

num(n); for(int i=0;i

>num[i]; cin>>target; searchRange(num,0,n-1,target,start,end); cout<

<<" "<

转载地址：http://hwpol.baihongyu.com/