二分法

admin 2022年1月6日01:36:10安全博客评论11 views1027字阅读3分25秒阅读模式

概念

二分法查找,也称为折半法,是一种在有序数组中查找特定元素的搜索算法。

思路

二分法查找的思路如下:

(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) //查找区间,以两个数据为例子,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;
}
}
}

例题

  1. 求开方
  2. 大于给定元素的最小元素
  3. 有序数组的 Single Element
  4. 第一个错误的版本
  5. 旋转数组的最小数字
  6. 查找区间

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

特别标注: 本站(CN-SEC.COM)所有文章仅供技术研究,若将其信息做其他用途,由用户承担全部法律及连带责任,本站不承担任何法律及连带责任,请遵守中华人民共和国安全法.
  • 我的微信
  • 微信扫一扫
  • weinxin
  • 我的微信公众号
  • 微信扫一扫
  • weinxin
admin
  • 本文由 发表于 2022年1月6日01:36:10
  • 转载请保留本文链接(CN-SEC中文网:感谢原作者辛苦付出):
                  二分法 http://cn-sec.com/archives/721954.html

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: