Question

关于数组算法的问题

给定一个数组，数组中的元素是升序排序出的，现输入一个数，如果这个数在数组中存在，则输出角标，如果这个数不在数组中，则判断此数在数组中所处的位置，并输出相邻两个数的角标。

Answer 1

二分该数的位置
输入数设为x，数组设为a,数组长度为n
若我们取a[mid]与x比较

由于a是升序的，a[mid]前面的数都比a[mid]小，所以若x>a[mid] 则x>a[mid]前面的所有数，我们想要的答案就在区间[mid+1, n]。
反之答案与[1,mid-1]之间，若a[mid]=x,就退出算法（找到答案），若a[mid]<x且a[mid+1]>x,则x相邻角标也已找到，就为mid与mid+1.
分析这个算法的时间复杂度，
判断答案在不在[l,r]中，取mid=（l+r）/2.这样花O(1)判断后即可锁定答案在[l,mid-1]还是在[mid+1,r]
这样设规模为n的问题时间耗费为T(n)
则由算法过程可知：T(n)=O(1)+T(n/2) , T(1)=O(0)
n=2时，T（2）=O（1）+O（0）=O（1）
n=4时，T（4）=O（1）+O（1）=O（2）
n=8时，T（8）=O（1）+O（2）=O（3）
可发现
0=log2(1),
1=log2(2),
2=log2(4),
3=log2(8).
用数学归纳法（详见《数据结构与算法初步》中“分治算法的时间复杂度计算”）即可证明该算法时间复杂度为O(log2(n)).

顺便给份代码(c++）：
#include<cstdio>
int main(){
int a[100005]={0,2,3,4,66,456,2222},n=6,x=1,ans,ret;//位置0按中国习惯不放数。
int l=1,r=6,mid;//搜索区间[1,6]
while(l<=r){
mid=(l+r)>>1;
if(a[mid]==x){ ans=mid;break; }
if(a[mid]<x && a[mid+1]>x){ ret=mid;break; }
if(a[mid]<x) l=mid;
else r=mid;
}
if(ans) printf("%d",ans);
else printf("%d %d",ret,ret+1);
}
注意，若查询的数没有前一个或后一个数，则会出错
如果为了简洁，用下面这个：
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
int a[100005]={0,2,3,4,66,456,2222},n=6,x=567,ans,ret;//位置0按中国习惯不放数。
ans=lower_bound(a+1,a+7,x)-a;
if(a[ans]==x) printf("%d",ans);
else printf("%d %d",ans-1,ans);
}
lower_bound返回（升序）数组中第一个大于等于x的数的指针

Answer 2

最简单的做法就是将输入值与数组中的元素依次对比。