文章目录
题目描述示例示例 1示例 2
题解代码
题目描述
给定已排好序的
n
n
n 个元素
a
[
0
:
n
−
1
]
a[0 : n - 1]
a[0:n−1] ，在这
n
n
n 个元素中找出某一特定元素
x
x
x 。
示例
输入
第一行输入数组元素个数
n
n
n第二行输入数组各个元素
a
[
0
]
.
.
.
a
[
n
−
1
]
{a[0] ... a[n - 1]}
a[0]...a[n−1]第三行输入所要找的元素
x
x
x 输出
输出元素
x
x
x 在数组中的下标，如果不存在则输出
−
1
-1
−1
示例 1
输入:
5
1 3 5 7 9
3
输出:
1
示例 2
输入:
6
1 5 6 10 12 20
9
输出:
-1
题解
首先可以采用顺序查找方法，逐个查找
a
[
0
:
n
−
1
]
{a[0 : n - 1]}
a[0:n−1] 中的元素，直至找出元素
x
x
x 或者搜索完整个数组。在最坏情况下，这样做的时间复杂度显然是
O
(
N
)
O(N)
O(N) 。
顺序查找没有利用数组元素有序的性质。二分查找采用分治策略，将
n
n
n 个元素分成个数大致相同的两部分，取
a
[
n
/
2
]
a[n / 2]
a[n/2] 与
x
x
x 比较。如果
x
x
x 等于
a
[
n
/
2
]
a[n / 2]
a[n/2] ，则找到
x
x
x ，算法结束。如果
x
x
x 小于
a
[
n
/
2
]
a[n / 2]
a[n/2] ，则在数组
a
a
a 的左半部分继续按照此算法继续搜索
x
x
x ；如果
x
x
x 大于
a
[
n
/
2
]
a[n / 2]
a[n/2] ，则在数组
a
a
a 的右半部分继续按照此算法继续搜索
x
x
x 。在最坏情况下，二分查找的时间复杂度是
O
(
l
o
g
N
)
{O(logN)}
O(logN) 。
当然，也可以构建哈希表来处理此问题，时间复杂度只是
O
(
1
)
{O(1)}
O(1) 级别。
代码
#include <iostream>
using namespace std
;
int iterate_binary_search(int *a
, int &n
, const int &x
);
int recursion_binary_search(int *a
, int &n
, const int &x
);
int recursion_auxiliary(int *a
, int &left
, int &right
, const int &x
);
const int size
= 100;
int main()
{
int n
= 0, i
= 0, a
[size
], x
= 0;
cin
>> n
;
for (i
= 0; i
< n
; i
++)
{
cin
>> a
[i
];
}
cin
>> x
;
cout
<< iterate_binary_search(a
, n
, x
) << endl
;
return 0;
}
int iterate_binary_search(int *a
, int &n
, const int &x
)
{
int index
= -1;
int left
= 0, right
= n
- 1, middle
= 0;
while (left
<= right
)
{
middle
= (left
+ right
) / 2;
if (x
== a
[middle
])
{
index
= middle
;
break;
}
if (x
> a
[middle
])
{
left
= middle
+ 1;
}
else
{
right
= middle
- 1;
}
}
return index
;
}
int recursion_binary_search(int *a
, int &n
, const int &x
)
{
int left
= 0, right
= n
- 1;
return recursion_auxiliary(a
, left
, right
, x
);
}
int recursion_auxiliary(int *a
, int &left
, int &right
, const int &x
)
{
if (left
> right
)
{
return -1;
}
int middle
= (left
+ right
) / 2;
if (x
== a
[middle
])
{
return middle
;
}
if (x
> a
[middle
])
{
left
= middle
+ 1;
}
else
{
right
= middle
- 1;
}
return recursion_auxiliary(a
, left
, right
, x
);
}
返回顶部
