二分查找
介绍
二分查找，也叫折半搜索、对数搜索。是用来在一个
有序
数组中查找一个数的算法。
例题
题目描述
给定一个
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
提示：
-
你可以假设
nu
m
s
nums
n
u
m
s
中的所有元素是
不重复
的。 -
nn
n
将在
[1
,
10000
]
[1, 10000]
[
1
,
1
0
0
0
0
]
之间。 -
nu
m
s
nums
n
u
m
s
的每个元素都将在
[−
9999
,
9999
]
[-9999, 9999]
[
−
9
9
9
9
,
9
9
9
9
]
之间。
解题思路
思路1：暴力
(
O
(
n
)
)
(O(n))
(
O
(
n
)
)
遍历数组，如果出现了
target
值则
返回其下标
，如果遍历完还没有出现
target
值则
返回-1
，因为整个数组需要遍历一遍，因此时间复杂度为
O
(
n
)
O(n)
O
(
n
)
。
代码
class Solution {
public:
int search(vector<int>& nums, int target) {
for(int i = 0; i < nums.size(); i ++) // 遍历数组
if(nums[i] == target) return i; // 如果出现了target值，返回下标
return -1; // 遍历完还没出现target值，返回-1
}
};
思路2：二分
(
O
(
l
o
g
n
)
)
(O(logn))
(
O
(
l
o
g
n
)
)
从题目中我们发现数组是
有序
的，符合二分查找的使用条件。假设数组长度为
n
，我们可以先看
nums[n / 2]
，假如
nums[n / 2] > target
，那么就意味着
nums[n / 2]
之后的所有数都大于
target
，我们只需要从
0
∼
n
/
2
0 \sim n / 2
0
∼
n
/
2
中去找
target
即可。否则我们就从
n
/
2
∼
n
−
1
n / 2 \sim n – 1
n
/
2
∼
n
−
1
中去找，当只剩下最后一个元素时，我们
判断它与target是否相等
，如果
相等就返回下标，否则返回-1
.因为我们每次都只会用到前一半或者后一半的数组，最后数组长度从
n
变成
1
，因此总共操作次数
k
符合
2
k
=
n
2^k = n
2
k
=
n
，因此
k = logn
，时间复杂度为
O
(
l
o
g
n
)
O(logn)
O
(
l
o
g
n
)
。
代码
class Solution {
public:
int search(vector<int>& nums, int target) {
int l = 0,r = nums.size() - 1; // 设l为左边界，r为右边界，从nums[]l~r]中查找target
while(l < r){ // 如果还剩下不止一个元素，则继续查找
int mid = l + r >> 1; // 求出l~r的中点
if(nums[mid] < target) l = mid + 1; // 假如中点值小于target，，就从nums[mid + 1,r]中查找target
else r = mid; // 否则从nums[l,mid]中查找target
}
if(nums[l] == target) return l; // 如果剩下的数 == target，返回下标
return -1;// 否则返回-1
}
};
二分思想
前面的例题应该已经让你对二分有个初步的概念。就是将一个
有序数组
分成两半，其中一半的元素都
<
=
m
i
d
<=mid
<
=
m
i
d
值，另外一半反之，因此只有一半是我们可能需要的，另一半我们可以直接舍弃。从广义上看，不仅是排序好的数组可以用二分，只要是左右两边具有不同的性质都可以用二分，排序好的数组中，
mid左边的数都<=mid
，
mid右边的数都>=mid
，这便是左右两边的不同性质，可以让我们对数组进行折半拆分。，例如
搜索旋转排序数组
，这个题目的数组虽然没有严格排序，但它依然可以用二分解答。
边界问题
整数二分有一个边界问题，那就是在
if(nums[mid] < target) l = mid + 1;
中能不能改成
l = mid
，答案是不可以，假如我们有一个从
1
∼
100
1 \sim 100
1
∼
1
0
0
内猜数字
target = 7
的程序代码如下：
#include <iostream>
using namespace std;
int main(){
int n =100;
int target = 7;
int l = 1,r = 100;
while(l < r){
cout << l << ' ' << r << endl; // 输出l 和 r
int mid = l + r >> 1;
if(mid < target) l = mid;
else r = mid;
}
cout << l;
return 0;
}
我们很容易发现程序陷入了死循环，因为当
l = 6,r = 7
时，，
mid = l + r >> 1 = 6
，
6 < 7
，因此
l = mid = 6
，因此陷入了死循环，归根结底是因为
mid = l + r >> 1
是
向下取整
的，因此当还剩2个元素的时候
l和mid有可能相等
，因此令
l = mid
会引发死循环，所以
l = mid + 1
在这份代码中是无法修改为
l = mid
的，其它情况也可以自由探索。