概念
二分法查找，也称为折半法，是一种在有序数组中查找特定元素的搜索算法。
思路
二分法查找的思路如下：
（1）首先，从数组的中间元素开始搜索，如果该元素正好是目标元素，则搜索过程结束，否则执行下一步。
（2）如果目标元素大于/小于中间元素，则在数组大于/小于中间元素的那一半区域查找，然后重复步骤（1）的操作。
（3）如果某一步数组为空，则表示找不到目标元素。
二分法查找的时间复杂度O(logn)。
框架
非递归方法:
区间问题
二分查找，要注意的地方
闭区间 [L,R]:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int binary_search(int a[],int size,int p)
{
int L = 0;
int R = size - 1;
while(L <= R)
{
int mid = L + (R - L)/2;
if(p == a[mid])
return mid;
else if(p > a[mid]){
L = mid +1;
}
else{
R = mid - 1;
}
}
}
|
左闭右开 [L,R)：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
int binary_search(int a[],int size,int p)
{
int L = 0;
int R = size - 1;
while(L < R)
{
int mid = L + (R -L)/2;
if(p == a[mid])
return mid;
else if(p < a[mid]){
R = mid;
}
else{
L = mid;
}
}
}
|
左开右开 (L ,R):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int binary_search(int a[],int size,int p)
{
int L = 0;
int R = size - 1;
while(R-L > 1){
int mid = L + (R-L)/2;
if(a[mid] == p)
return mid;
else if(p < a[mid]){
R = mid;
}
else{
L = mid;
}
}
}
|
例题
- 求开方
- 大于给定元素的最小元素
- 有序数组的 Single Element
- 第一个错误的版本
- 旋转数组的最小数字
- 查找区间
https://github.com/CyC2018/CS-Notes/blob/master/notes/Leetcode%20%E9%A2%98%E8%A7%A3%20-%20%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.md
参考文章:
算法-二分查找
二分查找，要注意的地方
FROM :blog.cfyqy.com | Author:cfyqy
评论