什么是二分查找？

二分法是计算机科学中最基本，最有用的算法之一，它描述了在有序集合中搜索特定值的过程。
经常使用的术语：

目标Target：你要查找的值
索引Index：你要查找的当前位置
左右指示符Left，Right：用来维持查找空间的指标
中间指示符Mid：用来应用条件来判断向左查找还是向右查找

二分查找运转方式

其实就是比大小，拿目标值Target与中间值Mid比较，如果条件不满足或值不相等，则删除目标值不可能存在的那一半，在可能存在的那一半继续查找，直到找到为止。

如何识别二分查找

二分法是一种每次比较之后都会把查找空间一分为二的算法。每次需要查找集合的索引或元素时应考虑二分法。当然，如果集合无序，还需要排序预处理。

二分查找三步骤

NO.1 预处理：对集合进行排序
NO.2 比较处理：目标值Target与集合的Mid比较
NO.3 处理后：选择合适的区间再比较

二分法的三个模板：

模板一：

def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    左闭右闭型
    """
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1
    while left <= right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    # End Condition: left > right
    return -1

这个模板是最基础的也是最标准的
查找条件可以在不与元素的两侧进行比较的情况下确定（或使用它周围的特定元素）。
不需要后处理，因为每一步中，你都在检查是否找到了元素。如果到达末尾，则知道未找到该元素

模板二：

def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    左闭右开型
    """
    if len(nums)==0:
        return -1
    left,right=0,len(nums)   # 右边索引取不到
    while left<right:
        mid=left+(right-left)//2
        if nums[mid]==target:
            return mid
        elif nums[mid]<target:
            left=mid+1
        else:
            right=mid
    if left!=len(nums) and nums[left]==target:   #跳出循环的条件是right==left，
        return left
    return -1
    两种情况都是lr索引相邻 ，target在r索引上。第一种情况是r索引在数组右边界(开区间)上，这种情况是lr重合的时候lr索引都是越界的。第二种情况是r索引不是数组右边界(开区间)，这种情况是当循环结束时lr索引重合的时候返回l索引上的target。。。(因为两个整数除二的时候总是偏向前面一个的当target在r索引的时候就很难在循环里面就能nums[middle]==target)

while(left < right) 的终止条件是 left == right，写成区间的形式就是 [left, right]，或者带个具体的数字进去 [2, 2]，这时候搜索区间非空，还有一个数 2，但此时 while 循环终止了。也就是说这区间 [2, 2] 被漏掉了，索引 2 没有被搜索，如果这时候直接返回 -1 就是错误的。

模板三：

def binarySearch(nums, target):
    """
    :type nums: List[int]
    :type target: int
    :rtype: int
    左闭右闭型
    """
    if len(nums) == 0:
        return -1

    left, right = 0, len(nums) - 1
    while left + 1 < right:
        mid = (left + right) // 2
        if nums[mid] == target:
            return mid
        elif nums[mid] < target:
            left = mid
        else:
            right = mid

    # Post-processing:
    # End Condition: left + 1 == right
    if nums[left] == target: return left
    if nums[right] == target: return right
    return -1