每日一道编程题：查找元素位置

题目

给定一个按照升序排列的有序数组和一个目标值，查找出这个目标值在有序数组中的第一个位置和最后一个位置。如果在数组中不存在目标值，则输出[-1,-1]。

输入格式

第一行有两个整数，第一个为目标值整数x，第二个为数组的长度n。
第二行有n个整数，按长序排列。

输出格式

参照样例

输入样例一

8 6
5 7 7 8 8 10

输出样例一

[4,5]

输入样例二

5 6
5 7 7 8 8 10

输出样例二

[1,1]

输入样例三

6 6
5 7 7 8 8 10

输出样例三

[-1,-1]

数据规模

1<=n<=10000

代码

#include <bits/stdc++.h>
using namespace std;
int a[10005];
int twofenfind1(int a[],int left,int right,int x)
{
if(left>right)
return -1;
int mid=left+(right-left)/2;
if(a[mid]==x)
{
if(a[mid-1]==x)
return twofenfind1(a,left,mid-1,x);
return mid;
} 
if(a[mid]>=x)
return twofenfind1(a,left,mid-1,x);
return twofenfind1(a,mid+1,right,x);
}
int twofenfind2(int a[],int left,int right,int x)
{
if(left>right)
return -1;
int mid=left+(right-left)/2;
if(a[mid]==x)
{
if(a[mid+1]==x)
return twofenfind2(a,mid+1,right,x);
return mid;
} 
if(a[mid]>=x)
return twofenfind2(a,left,mid-1,x);
return twofenfind2(a,mid+1,right,x);
}
int main()
{
int target,n;
cin>>target>>n;
for(int i=1; i<=n; i++)
cin>>a[i];
cout<<"["<<twofenfind1(a,1,n,target)<<","<<twofenfind2(a,1,n,target)<<"]";
return 0;
}

原文地址：https://blog.csdn.net/Python_enjoy/article/details/135906306

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！