计算二分查找中左或右的区别？

Question

这两种计算的中间位置有什么区别？

int mid = left + (right - left) / 2

和

int mid = right - (right - left) / 2;

Answer 1

说明

有无显着差异。通过一些示例数字来运行它并看看自己。

唯一的区别是它如何打破偶数上的联系，其中中间要么是左边一个，要么右边一个。

甚至是例子

例如，假设您有一个包含

8

数字（偶数）的数组。然后，中点将位于索引

3

或

4

，两者都有效。

第一个选项：

int mid = left + (right - left) / 2;
int mid = 0 + (7 - 0) / 2;
int mid = 7 / 2; // 3.5 before truncating
int mid = 3;

第二个选项：

int mid = right - (right - left) / 2;
int mid = 7 - (7 - 0) / 2;
int mid = 7 - 7 / 2;
int mid = 7 - 3;
int mid = 4;

奇怪的例子

对于奇数，它们都计算相同的数字：

0 - (8 - 0) / 2 = 4
8 - (8 - 0) / 2 = 4