关于C++二分查找算法的一个查询
关于C++二分查找算法的一个查询
提问于 2018-10-30 13:48:27
在Binary Search Algorithm中，
总体而言
if mid_value > search_element we set high = mid_pos-1 ;
else mid_value < search_element we set low = mid_pos+1 ;但是我刚刚修改了算法，像这样
if mid_value > search_element we set high = mid_pos ;
else mid_value < search_element we set low = mid_pos ;但是我的老师告诉我，binary search的标准算法是第一个，你写的也是一个搜索算法，但它不是一个二进制搜索算法。他说得对吗？
回答 2
Stack Overflow用户
发布于 2018-10-30 15:32:31
您的算法不正确：
案例:列表1，2，searchElem =2，低= 0，高=1
mid = (low+high)/2 = (0+1)/2 =0
mid < searchElem set low = mid更新mid = 0，high =1列表未更改
因此，您将以无限循环结束。
Stack Overflow用户
发布于 2018-10-30 14:02:34
我想你拿错了。
Binary Search Algorithm的基本工作流程：
Procedure binary_search
A ← sorted array
n ← size of array
x ← value to be searched
Set lowerBound = 1
Set upperBound = n
while x not found
if upperBound < lowerBound
EXIT: x does not exists.
set midPoint = lowerBound + ( upperBound - lowerBound ) / 2
if A[midPoint] < x
set lowerBound = midPoint + 1
if A[midPoint] > x
set upperBound = midPoint - 1
if A[midPoint] = x
EXIT: x found at location midPoint
end while
end procedure在这里，您可以看到midPoint = lowerBound + ( upperBound - lowerBound ) / 2、lowerBound = midPoint + 1和upperBound = midPoint - 1实际上做了什么。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53058133
复制相关文章
相似问题
腾讯云开发者
