#!/usr/bin/env python
# coding:utf-8


"""
二分查找模板分析

模板说明：
    你在网上看到的 99% 的二分查找问题会归结于这 3 个模板中的一个。
    有些问题可以使用多个模板来实现，但是当你做更多的练习时，你会注意到一些模板比其他模板更适合某些问题：
        模板 #1 和 #3 是最常用的，几乎所有二分查找问题都可以用其中之一轻松实现。
        模板 #2 更 高级一些，用于解决某些类型的问题。

3 个模板的不同之处在于：
    左、中、右索引的分配。
    循环或递归终止条件。
    后处理的必要性。
"""

"""
模板 #1 (left <= right)：
    二分查找的最基础和最基本的形式。
    查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
    不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素。


模板 #2 (left < right)：
    一种实现二分查找的高级方法。
    查找条件需要访问元素的直接右邻居。
    使用元素的右邻居来确定是否满足条件，并决定是向左还是向右。
    保证查找空间在每一步中至少有 2 个元素。
    需要进行后处理。 当你剩下 1 个元素时，循环 / 递归结束。 需要评估剩余元素是否符合条件。


模板 #3 (left + 1 < right)：
    实现二分查找的另一种方法。
    搜索条件需要访问元素的直接左右邻居。
    使用元素的邻居来确定它是向右还是向左。
    保证查找空间在每个步骤中至少有 3 个元素。
    需要进行后处理。 当剩下 2 个元素时，循环 / 递归结束。 需要评估其余元素是否符合条件。
"""

"""
时间和空间复杂度：
    时间：
        O(log n) —— 算法时间
        因为二分查找是通过对查找空间中间的值应用一个条件来操作的，并因此将查找空间折半，在更糟糕的情况下，我们将不得不进行 O(log n) 次比较，其中 n 是集合中元素的数目。
    
    空间：
        O(1) —— 常量空间
        虽然二分查找确实需要跟踪 3 个指标，但迭代解决方案通常不需要任何其他额外空间，并且可以直接应用于集合本身，因此需要 O(1) 或常量空间。
"""
