边界问题：

  • 边界问题涉及到一种特殊情况：由于偶数个元素时的中心Center / 2总是向下取整，所以我们会产生左右边界是否应该包含该中心Center的问题。

    1.左部分右边界包含Center：

    - 出口情况：

  • 在这种情况下，当元素个数N为2时，如{1, 2}，Left = 0；Center = 0，Right = Center = 0；

  • 此时，如果遍历出口已经存在Left == Right，则无需考虑Left > Right的情况，它是永远都不会出现的。

  • 如果遍历出口不存在Left == Right，则还必须考虑Left > Right的情况。因为该情况会在Left == Right时的下一次遍历出现。

    - 遍历情况：

  • 在这种情况下的遍历将始终包含Center元素。

    2.左部分右边界不包含Center：

    - 出口情况：

  • 在这种情况下，当元素个数N为2时，如{1, 2}，Left = 0；Center = 0，Right = Center - 1 = -1；

  • 此时，如果遍历出口已经存在Left == Right，则还必须考虑Left > Right的情况。该情况在N=2时一定会出现。

  • 如果遍历出口不存在Left == Right，则还必须考虑Left > Right的情况。因为该情况会在Left == Right时的下一次遍历出现。

    - 遍历情况：

  • 在这种情况下的遍历默认不会包含Center元素，除非在每一次遍历过程中都对Center索引位的值进行了相关操作。

    3.右部分左边界包含Center：

  • 由于Center向下取整，当元素个数N=2时，如{1, 2}，Left = Center = 0；Right = 1；

  • 此时，其左边界将无限制地为0，右边界也无限制地为1，从而造成死循环。故谈论右部分左边界包含Center值的行为是无意义的。

总结：

  • 结合上面的结论可以使我们在使用左边界索引、中心索引、右边界索引时规避数组越界的问题：
    • 当我们放任左边界Left > 右边界Right时，就很有可能造成数组的越界。因此：
      • 当我们包含Center且具有Left == Right的出口条件时，我们就可以不必考虑数组越界的问题；
      • 其余情况，我们都需要考虑Left > Right时可能造成的数组越界问题。
    • 当我们需要先对根操作然后再递归时，为了避免重复，就可以选择用不包含Center的写法；
    • 当我们不需要先对根进行操作时，就可以选择包含Center的写法，因为最后总会分治到根上，即在右侧分治时Left==Right的时候。