algorithm - 这个二进制搜索的伪代码是否正确？

Question

Boolean Binary Search (first,last)
if (last > first)
  return false
else
  Set middle to (first+last)/2
  Set result to list[middle].compareTo(item)
  if (result is equal to 0)
    return true
  else
    if (result < 0)
      Binary Search (first, middle - 1)
    else
      Binary Search(middle + 1, last)

“O”代表什么？如果是我们要查找的项目，是否需要将这段伪代码中的'If(result < O)'替换为'If(result > O)'？

Answer 1

此代码包含一个非常微妙的错误:(first + last)/2 如果 first 和 last 之和可能会导致溢出> 大于最大支持值。

更好的选择是使用 first + (last - first)/2

您可以在这里阅读更多相关信息: https://research.googleblog.com/2006/06/extra-extra-read-all-about-it-nearly.html