c++实现折半查找的非递归算法
时间: 2023-09-17 12:09:15 浏览: 63
折半查找,也称为二分查找,是一种在有序数组中查找特定元素的搜索算法。它的基本思想是将数组分成两个部分,判断要查找的元素在哪个部分,然后只在该部分继续查找,直到找到目标元素或者确定目标元素不存在为止。
以下是 c++ 实现折半查找的非递归算法:
```c++
int binarySearch(int arr[], int n, int target)
{
int left = 0, right = n - 1;
while (left <= right)
{
int mid = left + (right - left) / 2;
if (arr[mid] == target)
{
return mid;
}
else if (arr[mid] > target)
{
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return -1;
}
```
其中,arr 为有序数组,n 为数组长度,target 为要查找的目标元素。left 和 right 分别表示当前查找范围的左右边界,mid 表示当前查找范围的中间位置。
具体实现中,先初始化左右边界,然后在每次循环中计算中间位置 mid,根据 arr[mid] 和 target 的大小关系更新左右边界,直到找到目标元素或者确定目标元素不存在为止。如果最终找到目标元素,则返回其下标;否则返回 -1 表示未找到。