二分查找算法
百度百科算法效率O(log<sub>2</sub>n)（对数时间）
输入为一个有序的元素序列，如果要查找的元素包含在列表中，二分查找返回其位置，否则返回null
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；如果x<a[n/2],则只要在>数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
仅当列表是有序的时候，二分查找才是有效的
python实现
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
|
def binary_search(list_1, item):
low = 0
high = len(list_1)-1
while low <= high:
'''使用 // 整除运算符可以不用int进行类型转换'''
mid = (low + high)/2
guess = list_1[int(mid)]
if guess == item:
return int(mid)
if guess < item:
low = mid+1
if guess > item:
high = mid-1
return None
def main():
list_2 = [1,2,3,4,5,6,7,8,9]
print(binary_search(list_2, 8))
print(binary_search(list_2, 10))
main()
|
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
| #include<iostream>
#include<typeinfo>
using namespace std;
int binary_search(int a[9],int n,int x)
{
int mid;
int high,low=0;
int guess;
high = n-1;
while(low <= high)
{
mid = (high+low)/2;
guess = a[mid];
if(guess == x)
return mid;
if(guess > x)
high = mid-1;
if(guess < x)
low = mid+1;
}
return -1;
}
int main()
{
int temp;
int a[9] = {1,2,3,4,5,6,7,8,9};
cout<<sizeof(a)/sizeof(int)<<endl;
cout<<typeid(sizeof(a)/sizeof(int)).name()<<endl;
temp = binary_search(a,sizeof(a)/sizeof(int),5);
cout<<temp<<endl;
return 0;
}
|
类型名获取
使用头文件typeinfo下的typeid(parameter).name()获取类型名
