二进制搜索的时间复杂性是什么，它可以呼叫另一个辅助功能？
助手检索要在搜索功能中进行比较的值。这里是一个对象。
def get_val(mem, c):
if c == "n":
return mem.get_name()
elif c == "z":
return mem.get_zip()
在下面的辅助函数下面的函数中，每次迭代中都调用。这将影响二进制搜索的时间复杂性，还是仍然是O（log n）
def bin_search(array, c, s):
first = 0
last = len(array)-1
found = False
while( first<=last and not found):
mid = (first + last)//2
val = get_val(array[mid], criteria)
if val == s:
return array[mid]
else:
if s < val:
last = mid - 1
else:
first = mid + 1
return None
The helper retrieves value to be compared in the search function. here mem is an object.
def get_val(mem, c):
if c == "n":
return mem.get_name()
elif c == "z":
return mem.get_zip()
In the function below the helper function above is called in each iteration. Will this impact the time-complexity of the binary search or will it still be O(log n)
def bin_search(array, c, s):
first = 0
last = len(array)-1
found = False
while( first<=last and not found):
mid = (first + last)//2
val = get_val(array[mid], criteria)
if val == s:
return array[mid]
else:
if s < val:
last = mid - 1
else:
first = mid + 1
return None
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
由于您正在调用
get_val（）根据二进制搜索的迭代一次，因此总的时间复杂性应为o（log n * f（x）），
其中 f（x）是
get_val（）的时间复杂性。如果这是恒定的（不取决于输入，例如array的内容），则实际上您的总时间复杂性仍然是 o（log n）。Since you are calling
get_val()once per iteration of your binary search, the total time complexity should beO(log n * f(x)),
where f(x) is the time complexity of
get_val(). If this is constant (does not depend on the input, such as the contents ofarray), then indeed your total time complexity is still O(log n).