leetcode 704. 二分查找
- leetcode 704. 二分查找 | 简单难度
- 1. 题目详情
- 1. 原题链接
- 2. 基础框架
- 2. 解题思路
- 1. 题目分析
- 2. 算法原理
- 3. 时间复杂度
- 3. 代码实现
- 4. 知识与收获
leetcode 704. 二分查找 | 简单难度
1. 题目详情
给定一个 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
提示:
你可以假设 nums 中的所有元素是不重复的。
n 将在 [1, 10000]之间。
nums 的每个元素都将在 [-9999, 9999]之间。
1. 原题链接
leetcode 704. 二分查找
2. 基础框架
● Cpp代码框架
class Solution {
public:
int search(vector<int>& nums, int target) {
}
};
2. 解题思路
1. 题目分析
(
1
)
(1)
(1) 本题要在升序数组nums
中查找目标值target
;找到了就返回target
所在位置下标,否则返回-1。
(
2
)
(2)
(2) 暴力解法:啥都不考虑,直接从左向右遍历数组nums
,找到了目标值target
就返回其下标。如果遍历完数组nums
还是没有找到就返回-1;
(
3
)
(3)
(3) 暴力解法每次判断只能舍弃1个元素,时间复杂度是
O
(
n
)
O(n)
O(n)。
2. 算法原理
(
1
)
(1)
(1) 优化暴力枚举:暴力解法没有考虑数组nums
元素是有序的,我们我们根据这一规则看看能不能把数组分成两部分。
为了一般性,我们不使用具体的例子,而是假设一个长度为n
的数组nums
。
定位这个数组中任意位置的一个元素,假设下标为i
,那么这个元素就是nums[i]
。
nums[i]
可以把数组nums
分成左右两个部分吗?
很明显是可以的:[0, i -1]
范围的元素都小于nusm[i]
,[i + 1, n - 1]
范围的元素都大于nums[i]
。
至此,我们就根据升序数组的规则,每次都能把数组nums
分成左右含义不同的两部分。
经过上述分析,我们可以在[0, n - 1]
范围内任意找一个位置作为判断点,可是具体来说,找哪个位置效率最高呢?
是中点处?是三等分处?还是其他的?
可以证明的是,每次都找中点位置作为判断点效率是最高的
O
(
l
o
g
2
n
)
O(log_2n)
O(log2n)。
( 2 ) (2) (2) 二分:
- 初始化左边界left = 0, 右边界right = n - 1;
- mid = left + (right - left) / 2;
- nums[mid] < target, left = mid + 1;
- nums[mid] > target, right = mid - 1;
- nums[mid] == target, 返回结果;
- left <= right时一直进行2、3、4、5步;
( 3 ) (3) (3) 其实循环条件也可以是left < right,此时循环结束时left和right一定是相同的(即left与right相遇位置),并且此位置没有进行判断,循环结束时额外判断一下即可。
3. 时间复杂度
二分 O ( l o g 2 n ) O(log_2n) O(log2n)
每次选取
[left, right]
范围中点,每次判断都能舍弃一半元素直到找到目标或找不到;
证明:
长度为n的数组,设经过x次折半后长度变为1。那么 2 x = n 2^x=n 2x=n,即 x = l o g 2 n x=log_2n x=log2n
3. 代码实现
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0, r = nums.size() - 1;
while(l <= r){
int mid = l + (r - l + 1) / 2;
if(nums[mid] > target) r = mid - 1;
else if(nums[mid] < target) l = mid + 1;
else return mid;
}
return -1;
}
};
4. 知识与收获
( 1 ) (1) (1) 二分的本质是根据题目规则(升序、非递减、连续等)找出二段性,即根据规则能把数组分成左右两个含义不同的区间。
T h e The The E n d End End