二分法查找又称折半查找，它是一种效率较高的查找方法。二分法查找要求线性表是有序表， 即表中结点按关键字有序，并且要用向量作为表的存储结构。二分法也叫作折半查找法，我感觉这个算法是最简单的一个算法没有之一，理解起来也很容易。
二分法查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大 量的结点。因此，二分法查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。 对那些查找少而又经常需要改动的线性表，可采用链表作为存储结构，进行顺序查找。链表上无法 实现二分法查找。
1 #include<iostream> 2 using namespace std; 3 4 typedef struct 5 { 6 int data; //关键字域 7 char other; 8 }elemtype,*elemptr; 9 10 typedef struct 11 { 12 elemptr p; 13 int length; 14 }List; 15 16 void push(List &l) 17 { 18 cout<<"请输入插入数据的个数:"<<endl; 19 int n; 20 cin>>n; 21 l.length = n; 22 l.p = new elemtype[n+1]; 23 cout<<"请依次输入这"<<n<<"个数据"<<endl; 24 for(int i=1;i<=n;i++) 25 { 26 int j; 27 cin>>j; 28 l.p[i].data = j; 29 } 30 } 31 int mysearch(List l,int data) 32 { 33 int low = 1,high = l.length; 34 while(low<=high) 35 { 36 int mid = (low+high)/2; 37 if(l.p[mid].data>data) 38 { 39 high = mid-1; 40 }else if(l.p[mid].data<data) 41 { 42 low = mid+1; 43 }else{ 44 return mid; 45 } 46 } 47 return 0; 48 49 } 50 int main() 51 { 52 List l; 53 push(l); //默认升序排序 54 cout<<"请输入要查找的数:"; 55 int m; 56 cin>>m; 57 int s=mysearch(l,m); 58 cout<<endl; 59 if(s!=0) 60 cout<<"位置:"<<s; 61 else{ 62 cout<<"没有查找到！"; 63 } 64 65 return 0; 66 }
二叉排序树又称为二叉查找树，其定义为二叉排序树或者是一棵空二叉树，或者是具有如下性 质（BST性质）的二叉树：
从二叉排序树的概念可以看得出来，二叉排序树的左子树和右子树也是一颗二叉排序树。所以要注意一种递归的思想。
二叉排序树的插入和创建都是基于查找，创建就是从一个空节点不断地插入最后构成一个二叉排序树，二插入的时候要查找到自己的位置。
1 #include<iostream> 2 using namespace std; 3 4 typedef struct 5 { 6 int data; 7 char other; 8 }elemtype; //二叉树节点的数据类型 9 10 typedef struct BiNode 11 { 12 elemtype ptr; 13 struct BiNode * lchild,*rchild; 14 }BiNode,*BiTree; 15 //二叉排序树的插入 16 void InsertBiTree(BiTree &t,int data) 17 { 18 if(!t) 19 { 20 BiTree p =new BiNode; 21 p->ptr.data = data; 22 p->lchild = NULL; 23 p->rchild = NULL; 24 t =p; 25 } 26 else if(data>t->ptr.data){ 27 InsertBiTree(t->rchild,data); 28 }else{ 29 InsertBiTree(t->lchild,data); 30 } 31 } 32 // 基于二叉排序树的创建 33 34 void createBiTree(BiTree &t) 35 { 36 t =NULL; 37 elemtype elem; 38 cin>>elem.data; 39 while(elem.data!=-1) //-1是结束标志符 40 { 41 InsertBiTree(t,elem.data); 42 cin>>elem.data; 43 } 44 45 } 46 // 二叉排序树的查找，根据关键字查找之后可以查看其他数据 47 BiTree searchBiTree(BiTree t,int data) 48 { 49 if(!t||data ==t->ptr.data) 50 return t; 51 if(data>t->ptr.data) 52 return searchBiTree(t->rchild,data); 53 else 54 return searchBiTree(t->lchild,data); 55 } 56 57 void xz(BiTree t) 58 { 59 if(t){ 60 xz(t->lchild); 61 cout<<t->ptr.data<<" "; 62 xz(t->rchild); 63 } 64 } 65 int main() 66 { 67 BiTree tree; 68 createBiTree(tree); 69 xz(tree); 70 cout<<"请输入要插入的个数:"; 71 int counts; 72 cin>>counts; 73 for(int i=0;i<counts;i++) 74 { 75 cout<<"请输入第"<<i+1<<"个数:"; 76 int data; 77 cin>>data; 78 InsertBiTree(tree,data); 79 } 80 xz(tree); 81 82 return 0; 83 }
原文：https://www.cnblogs.com/g414056667/p/13697978.html