已知有如下两种搜索策略:
①bool Search1(int a[], int n, int target, int &pos)
{
int i;
for (i = 0; i < n; i++)
if (a[i] == target)
{
pos = i;
return true;
}
pos = -1;
return false;
}
②bool Search2(int a[], int n, int target, int &pos)
{
int f = 0, e = n - 1, m;
while (f < e)
{
m = (f + e) / 2;
if (target > a[m])
f = m + 1;
else if (target < a[m])
e = m - 1;
else
{
pos = m;
return true;
}
}
pos = -1;
return false;
}
请使用大O标记法给出它们各自的时间复杂度,哪种策略更优?
策略②是否适用于有序的单向链?简述你的理由。
查看答案和解析【26考研辅导课程推荐】:26考研集训课程,VIP领学计划,26考研VIP全科定制套餐(公共课VIP+专业课1对1) , 这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,可直接咨询在线客服老师领取大额优惠券。
启航教育热门私房课
MORE小班面授 名额有限 抢先体验
编辑推荐
最新内容