基础算法之二分查找

浏览数：16 / 时间：2015年06月08日

二分查找

利用分治法，逐渐苏小查找范围，适用于有序数组。

时间复杂度是O(log2N).

PS:二分查找算法的判定过程实际上可以借助一棵平衡二叉树来描述，中间位置的关键字可以看成二叉树的根节点。

C++代码如下：

技术分享 
 1 #include <iostream>
 2 using namespace std;
 3 template<class DataType>  int  binSearch(DataType key[],int n,DataType k)
 4 {
 5     int low=0,high=n-1;
 6     int mid;
 7     while(low<=high)
 8     {
 9         mid=(low+high)/2;
10         if(k == key[mid])
11         {
12             return mid;
13         }
14         else if(k>key[mid])
15         {
16             low=mid+1;
17         }
18         else
19         {
20             high=mid-1;
21         }
22     }
23 
24     return NULL;
25 }
26 
27 int main()
28 {
29     int data[] = {12,23,24,34,45,67,78,89,99};
30     int key;
31     cout<<"请输入要查找的数字： ";
32     cin>>key;
33     cout<<endl;
34     int result = binSearch(data,10,key);
35     cout<<"您要查找的数字是： "<<key<<"，它的位置是： "<<result+1<<endl;
36     return 0;
37 }
View Code

 

郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。

标签： 编程语言 Java C C# Javascript js Python Ruby Spring 程序 VB

相关文章

随机文章

您可能还喜欢

您可能还喜欢