二分查找算法
百度百科算法效率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()获取类型名
