本文实例讲述了C++二分法在数组中查找关键字的方法。分享给大家供大家参考。具体如下：
?
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
/*
此程序演示了二分法查找算法(针对按从小到大排列的数组)的实现。
*/
#include <iostream>
using namespace std;
/*
功能： 实现数组的二分法查找(只算法只适合按从小到大排列的数组)
返回值：关键字在数组中的下标, 返回-1表示未找到
a[]: 要搜索的数组
len: 数组元素个数
key: 要查找的关键字
*/
int binSearch(int a[], int len, int key)
{
int i = len / 2;
int ii = 0;
if(len < 1)
return -1;
if((key > a[i]) && (len - i > 0))
{
ii = binSearch(a+i+1, len - i - 1, key); // 在后半段数组中查找
if(ii != -1)
return ii + i + 1; // 加上数组前半段的长度
else
return -1;
}
else if(key < a[i] && i > 0) // 在前半段数组中查找
return binSearch(a, i, key);
else if(key == a[i])
return i; // 返回关键字在数组中的下标
else
return -1; // 未在数组中找到关键字
}
int main()
{
int a[] = {2, 4, 5, 20, 24, 35, 66, 78, 98};
int len = sizeof(a) / sizeof(int);
int i, key = -1;
while(1)
{
cin>>key;
i = binSearch(a, len, key);
printf("%d\\n", i);
if(key > 100)
break;
}
return 0;
}
|
相关文章
猜你喜欢
- 个人服务器网站搭建：如何选择合适的服务器提供商？ 2025-06-10
- ASP.NET自助建站系统中如何实现多语言支持？ 2025-06-10
- 64M VPS建站：如何选择最适合的网站建设平台？ 2025-06-10
- ASP.NET本地开发时常见的配置错误及解决方法？ 2025-06-10
- ASP.NET自助建站系统的数据库备份与恢复操作指南 2025-06-10
