C++ 迭代与递归方式分别实现二分查找
文章目录
C++ 迭代与递归方式分别实现二分查找0.前言1.迭代方式二分查找2.递归方式二分查找
0.前言
查找算法是一种常用算法，查找算法即从给定的数组中，找出要查找的元素第一次出现的位置，如果数组中该元素不存在，返回 -1。 使用二分查找的注意事项： 必须是有序序列才可以使用二分查找。
1.迭代方式二分查找
int binarySearch(std
::vector
<int>& arr
, const int value
){
int head
= 0;
int tail
= arr
.size() - 1;
int half
= (head
+ tail
) / 2;
while (head
<= tail
)
{
if (arr
.at(half
) > value
)
{
tail
= half
- 1;
half
= (head
+ half
) / 2;
}else if(arr
.at(half
) < value
){
head
= half
+ 1;
half
= (head
+ tail
) / 2;
}else{
return half
;
}
}
return -1;
}
2.递归方式二分查找
int binarySearch_recursive(const vector
<int>& arr
, const int head
, const int tail
, const int value
){
int half
= (head
+ tail
) / 2;
if(arr
.at(half
) > value
){
return binarySearch_recursive(arr
, head
, half
-1, value
);
}else if(arr
.at(half
) < value
)
{
return binarySearch_recursive(arr
, half
+1, tail
, value
);
} else
{
return half
;
}
return -1;
}
