【笔试题】 二分查询 | 在给定排序数组中查找目标值,存在返回其索引,不存在返回其待插入的位置(使插入后任然有序)
2023-09-27 14:28:31 时间
笔试题:给定一个排序数组和一个目标值,在数组中找到其目标值,并返回其索引。如果目标值不存在,则返回它按顺序插入的位置。
设计合适的数据结构
根据题目要求,在返回的下标中有两种属性:
- 结点存在,返回结点下标。
- 结点不存在,返回待插入的下标位置。
struct Result
{
int index; // 结点下标
bool falg; // 标记
};
如果 falg = true,则找到目标结点。
如果 falg = false, 则返回待插入位置。
递归:
struct Result
{
int index;
bool falg;
};
Result FindVal(int* ar, int left, int right, int val)
{
Result res = { -1,false };
int mid = (right - left) / 2 + left;
if (left <= right)
{
if (val < ar[mid])
{
res = FindVal(ar, left, mid - 1, val);
}
else if (ar[mid] < val)
{
res = FindVal(ar, mid + 1, right, val);
}
else
{
res.index = mid;
res.falg = true;
}
}
if (!res.falg && res.index == -1)
{
res.index = mid;
}
return res;
}
Result BinFindVal(int* ar, int n, int val)
{
Result res = { -1,false };
if (ar!= NULL && n > 1)
{
res = FindVal(ar, 0, n-1, val);
}
return res;
}
非递归:
Result NiceFindVal(int* ar, int n, int val)
{
Result res = { -1,false };
int low = 0, high = n;
while (low <= high)
{
int mid = (high - low) / 2 + low;
if (val < ar[mid])
{
high = mid - 1;
}
else if (ar[mid] < val)
{
low = mid + 1;
}
else
{
res.index = mid;
res.falg = true;
break;
}
}
return res;
}
Result NiceBinFindVal(int* ar, int n, int val)
{
Result res = { -1,false };
if (ar != NULL && n > 1)
{
res = FindVal(ar, 0, n - 1, val);
}
return res;
}
测试用列
int main()
{
int ar[] = { 12,23,34,45,56,67,78,89,90,100 };
int n = sizeof(ar) / sizeof(ar[0]);
int val;
while (cin >> val, val != -1)
{
Result res = BinFindVal(ar, n, val);
cout << res.falg << " " << res.index << "\t";
res = NiceBinFindVal(ar, n, val);
cout << res.falg << " " << res.index << endl;
}
return 0;
}
相关文章
- ElasticSearch索引库维护
- 一句口诀教你辨别索引失效七大场景
- mysql 索引与优化like查询
- 【python】pandas 的 apply函数方法 如何获取当前行的行索引
- 索引(四)
- MySQL not exists 真的不走索引么?
- MongoDB系列四(索引).
- mysql数据库性能优化(包括SQL,表结构,索引,缓存)
- php数组操作之获取数组元素索引(键)值【转】
- 2022-11-30 mysql-innodb-索引-分析
- mysql -- 索引
- 深入Lucene索引机制
- react列表key满足这些条件可以直接使用数组索引
- 如何检测MySQL是否命中索引?
- 【mysql我能讲两小时001】mysql使用的索引数据结构是什么?