TA的每日心情 | 开心 2021-12-13 21:45 |
---|
签到天数: 15 天 [LV.4]偶尔看看III
|
二分查找算法是在有序数组中用到的较为频繁的一种算法,在未接触二分查找算法时,最通用的一种做法是,对数组进行遍历,跟每个元素进行比较,其时间为O(n).但二分查找算法则更优,因为其查找时间为O(lgn),譬如数组{1, 2, 3, 4, 5, 6, 7, 8, 9},查找元素6,用二分查找的算法执行的话,其顺序为:
1.第一步查找中间元素,即5,由于5<6,则6必然在5之后的数组元素中,那么就在{6, 7, 8, 9}中查找,
2.寻找{6, 7, 8, 9}的中位数,为7,7>6,则6应该在7左边的数组元素中,那么只剩下6,即找到了。
二分查找算法就是不断将数组进行对半分割,每次拿中间元素和goal进行比较。
#include
<
iostream
>
using
namespace
std;
//
二分查找
int
binary_search(
int
*
a,
int
len,
int
goal);
int
main()
{
const
int
LEN
=
10000
;
int
a[LEN];
for
(
int
i
=
0
; i
<
LEN; i
++
)
a
=
i
-
5000
;
int
target
=
0
;
int
index
=
binary_search(a, LEN, target);
if
(index
!=
-
1
)
cout
<<target
<<
"
在数组中的下标为
"
<<
index
<<
endl;
else
cout
<<
"
不存在
"
<<target
<<
endl;
return
0
;
}
int
binary_search(
int
*
a,
int
len,
int
goal)
{
int
low
=
0
;
int
high
=
len
-
1
;
while
(low
<=
high)
{
int
middle
=
(high - low) / 2 + low
; // 直接使用(high + low) / 2 可能导致溢出
if
(a[middle]
==
goal)
return
middle;
//
在左半边
else
if
(a[middle]
>
goal)
high
=
middle
-
1
;
//
在右半边
else
low
=
middle
+
1
;
}
//
没找到
return
-
1
;
}
|
|