输入: nums = [-1,0,3,5,9,12], target = 9
输出: 4
解释: 9 出现在 nums 中并且下标为 4

算法描述：

• 先从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；
• 如果目标元素大于中间元素，则在数组大于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
• 如果目标元素小于中间元素，则在数组小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。
• 如果在某一步骤数组为空，则代表找不到。

复杂度分析

• 平均时间复杂度： $O(logN)$
• 最坏时间复杂度： $O(logN)$
• 最优时间复杂度： $O(1)$

空间复杂度

• 迭代: $O(1)$
• 递归： $O(logN)$（无尾调用消除）

后面的复杂度也是类似的，不再赘述。

这种搜索算法每一次比较都使搜索范围缩小一半，是典型的二分查找。

这个是二分查找中最简答的一种类型了，我们先来搞定它。 我们来一个具体的例子，假设 nums 为 [-1,0,3,5,9,12]， target 为 9。

• 刚开始数组中间的元素为 3。
• 9 > 3 ，由于 3 左边的数字都小于 9 ，因此不可能是答案。我们将范围缩写到了 3 的右侧。
• 此时中间元素为 5。
• 5 > 3，由于 5 左边的数字都小于 9 ，因此不可能是答案。我们将范围缩写到了 5 的右侧。
• 此时中间元素为 9，正好是我们要找的target，返回其索引 4 即可。

如何将上面的算法转换为容易理解的可执行代码呢？

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