704. 二分查找

Problem: 704. 二分查找

🐷我的leetcode主页

题目

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

示例 1:

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

输入: nums = [-1,0,3,5,9,12], target = 2
输出: -1
解释: 2 不存在 nums 中因此返回 -1
提示：

1. 你可以假设 nums 中的所有元素是不重复的。

2. n 将在 [1, 10000]之间。

3. nums 的每个元素都将在 [-9999, 9999]之间。

分类

二分查找

思路

什么是二分查找

二分查找是一种查找算法，它的基本思想是：通过比较元素的大小来缩小查找范围，直到找到目标元素或查找范围为空。

场景样例：

1. 假设要在电话簿中找一个名字以 K 打头的人，（现在谁还用电话簿！）可以从头开始翻页，直到进入以 K 打头的部分。但你很可能不这样做，而是从中间开始，因为你知道以 K 打头的名字在电话簿中间。所以你会直接从中间开始找。

2. 两个人玩游戏，A想一个1-100的数字(比如是60)，B来猜。

如果B从1开始猜，一直猜到99才能猜到，那么时间复杂度是O(n)

如果B从50开始猜，A会告诉B猜小了，那么B肯定会在50-100里面猜，那么就排除了一半1-50的数字

B再从75开始猜，A会告诉B猜大了，下次一B肯定在50-75里面猜，又排除了一半75-100的数字

这样依次类推，最终最多猜测O(logn)次，就能猜到最终共的答案。

如何理解时间复杂度

大 O 表示法指出了最糟情况下的运行时间

比如上面的例子，1-100采用线性放大依次猜，猜到100才能猜对的话，那么就需要猜测n次，所以复杂度是O(n);
如果采用二分查找，那么最多需要猜测100对2取对数的次数，那么时间复杂度是O(logn)。

通俗理解的话可以理解为操作数

比如要在一张正方形的纸上面画16个格子，那么最坏情况下，一个一个画，需要画16次，所以时间复杂度是O(n)。

如果采用折叠的方式，对折一次，产生2个格子，两次产生4个格子，3次产生8个格子，4次产生16个格子，那么时间复杂度是O(logn)。

解题方法

Code

    def search(self, nums, target):""":type nums: List[int]:type target: int:rtype: int"""low = 0high = len(nums) - 1while low <= high:mid = (low + high) // 2if nums[mid] == target:return midelif nums[mid] < target:low = mid + 1else:high = mid - 1return -1