首页 > 代码库 > 数据结构--二分查找
数据结构--二分查找
二分法查找(折半查找)的基本思想:
前提:顺序存储且元素有序
(1)确定该区间的中点位置:mid=(low+high)/2
min代表区间中间的结点的位置,low代表区间最左结点位置,high代表区间最右结点位置
(2)将待查a值与结点mid的关键字(下面用R[mid].key)比较,若相等,则查找成功,否则确定新的查找区间:
如果R[mid].key>a,则由表的有序性可知,R[mid].key右侧的值都大于a,所以等于a的关键字如果存在,必然在R[mid].key左边的表中。这时high=mid-1
如果R[mid].key<a,则等于a的关键字如果存在,必然在R[mid].key右边的表中。这时low=mid
如果R[mid].key=a,则查找成功。
(3)下一次查找针对新的查找区间,重复步骤(1)和(2)
(4)在查找过程中,low逐步增加,high逐步减少,如果high<low,则查找失败。
平均查找长度=Log2(n+1)-1
注:虽然二分法查找的效率高,但是要将表按关键字排序。而排序本身是一种很费时的运算,所以二分法比较适用于顺序存储结构。为保持表的有序性,在顺序结构中插入和删除都必须移动大量的结点。因此,二分查找特别适用于那种一经建立就很少改动而又经常需要查找的线性表。
下面是二分查找的非递归、递归的python实现:
#!/use/bin/env python
#encoding=gbk
"""The array is ordered, binary search"""
def
binarySearch():
list
=
[
-
7
,
-
5
,
-
3
,
0
,
1
,
3
,
5
,
7
]
target
=
7
low
=
0
high
=
len
(
list
)
count
=
0
while
low <
=
high:
count
+
=
1
mid
=
(low
+
high)
/
2
if
list
[mid]
=
=
target:
return
list
[mid], count
elif
list
[mid] > target:
high
=
mid
-
1
else
:
low
=
mid
+
1
return
None
, count
def
iter
(low, high, count,
list
, target):
mid
=
(low
+
high)
/
2
count
+
=
1
if
list
[mid]
=
=
target:
return
target,count
elif
list
[mid] > target:
return
iter
(low, mid
-
1
, count,
list
, target)
else
:
return
iter
(mid
+
1
, high, count,
list
, target)
"""The array is ordered, binary search interation."""
def
binarySearchIte():
list
=
[
-
7
,
-
5
,
-
3
,
0
,
1
,
3
,
5
,
7
]
target
=
7
return
iter
(
0
,
len
(
list
)
-
1
,
0
,
list
, target)
if
__name__
=
=
‘__main__‘
:
element,count
=
binarySearch()
print
"search element: %d\nsearch count:%d"
%
(element,count)
element,count
=
binarySearchIte()
print
"search element: %d\nsearch count:%d"
%
(element,count)
数据结构--二分查找
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。