本文共 1210 字，大约阅读时间需要 4 分钟。

查找一个数

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

示例 1:

输入: 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]
   
     right    return -1
   

参考

力扣（LeetCode） (leetcode-cn.com)]

转载地址：http://idyzi.baihongyu.com/