为什么二分搜索算法使用下限而不是上限-不在半开范围内 [英] Why does Binary search algorithm use floor and not ceiling - not in an half open range

问题描述

例如，当我们有一个索引从0到 n 的数组时. 当我在计算中间索引时使用使用下限或上限的二分搜索时，得到相同的结果.

When we have an array with indexes from 0 to n for example. when I use the Binary search using floor or ceiling when calculating the middle index I get the same out put.

int middle = ceiling((left + right)/2);

int middle = ceiling ((left+right)/2);

请问有理由在天花板上铺地板吗? 使用天花板会发生什么错误?

Is there a reason using floor over ceiling ? what bug will happen using the ceiling ?

推荐答案

复杂度没有区别.两种变体都是log(n).

There's no difference in complexity. Both variants are log(n).

根据其余的实现，如果您的数组看起来像这样，则可能会得到不同的结果

Depending on the rest of your implementation, you may get a different result if your array looks for instance like

0 1 1 1 1 2

并查找1的索引.

这篇关于为什么二分搜索算法使用下限而不是上限-不在半开范围内的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！