数据结构 |
您所在的位置：网站首页 › 有序数组的二分查找 › 数据结构 |
|
目录 减而治之 应用 细节 函数分析如下 函数代码 全部代码 结果截图 练习 减而治之“减”是减小问题规模，“治”是解决。减而治之是分而治之的特例，不同的是减而治之可以排除一部分，在可能存在答案的子问题中寻找。 应用在有序数组中查找一个数（二分下标），在某个整数范围内查找一个整数（二分范围）。 细节循环可以继续的条件，一般为while(low>1 上取整也是可以的，例如，mid = (low+high+1)/2 以在有序数组中查找一个数为例 函数分析如下Binary_search(SqList L,ElemType key) 参数：顺序表L，待查关键字 功能：查找key 时间复杂度：O(logn) 每次和中间值比较，相同返回下标，不相同调整边界。 函数代码 //二分查找函数 int Binary_search(SqList L,ElemType key) { int low = 0;int mid = 0;int high = L.length-1; while(lowL.data[mid]) { low = mid+1; } else { high = mid-1; } } return -1; } 全部代码 /* Project: binary_search(数据结构-二分查找) Date: 2018/10/26 Author: Frank Yu 重点： Binary_search(SqList L,ElemType key) 参数：顺序表L，待查关键字 功能：查找key 时间复杂度：O(logn) 基础函数： CreatList(SqList &L,int n) 参数：顺序表L，顺序表长度n 功能：创建长度为的顺序表 时间复杂度：O(n) InitList(SqList &L) 参数：顺序表L 功能：初始化 时间复杂度:O(1) InsertList(SqList &L,int i,ElemType e) 参数:顺序表L,位置i,元素e 功能：位置i处插入元素e 时间复杂度:O(n) ListDelete(SqList &L,int i) 参数:顺序表L,位置i 功能：删除位置i处元素 时间复杂度:O(n) LocateElem(SqList L,ElemType e) 参数:顺序表L,元素e 功能：返回第一个等于e的元素的位置 时间复杂度:O(n) PrintList(SqList L) 参数:顺序表L 功能：遍历L，并输出 */ #include #include #include #include #include #include #define MaxSize 100 #define ElemType int #define Status int using namespace std; //顺序表数据结构 typedef struct { ElemType data[MaxSize];//顺序表元素 int length; //顺序表当前长度 }SqList; //***************************基本操作函数*******************************// //初始化顺序表函数，构造一个空的顺序表 Status InitList(SqList &L) { memset(L.data,0,sizeof(L));//初始化数据为0 L.length=0; //初始化长度为0 return 0; } //创建顺序表函数 初始化前n个数据 bool CreatList(SqList &L,int n) { if(nMaxSize)false;//n非法 for(int i=0;i |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |