查找：根据某个给定值K，从集合R中找到与K相同记录，这就是查找。
静态查找：就是数据制作好后，不会在改动，只是查找，没有删除和插入。比如字典就是静态查找，字典制作好后，字不会在变动，用时查一下。
这类静态查找算法，数据一般可以放入数组中，先将数据全部写入数组，再来获取。
下面写个顺序查找来实现的代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
// 梁笔记 typedef struct LNode* List; struct LNode{ ElementType Element[MAXSIZE]; int Length; }; int SequentialSearch(List Tb1, ElementType K){ int i; Tb1->ElementTypep[0] = k; for(i = Tb1->Length; Tb1->Element[i]!=K; i--); return; } |
以上顺序代码有1个关键是，将数组0下标位置元素当“哨兵”，这是一个设计技巧。好处就是在for循环体内不用每次判断下标。
当找到时就返回找到的下标，当没有找到就会找到0下标，返回0就代表没有找到。
可以看出顺序查找算法时间复杂度是O(n)，最好情况就是第一个找到，最坏情况就是最后一个找到，平均时间复杂度是是O(n/2)。
有没有更好的查找算法？
有的，二分查找会比顺序查找更快。
二分查找也称折半查找（Binary Search），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。
下面写用二分查找代码：
|
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 |
// 梁笔记 // https://zouzhongliang.com typedef struct LNode* List; struct LNode{ ElementType Element[MAXSIZE]; int Length; }; int BinarySearch(List Tb1, ElementType K){ int low = 0; int high = Tb1->Length; // int pos; while (low<=high) { pos = (low + high) / 2; if (Tb1->Element[pos] == K)return pos; else if (Tb1->Element[pos] < K) { low = pos + 1; } else if (Tb1->Element[pos] > K) { high = pos - 1; } } return -1; } |
二分查找前提是数据都排序好，具体二分查找也可以看这篇：二分查找算法
二分查找算法复杂度为对数时间复杂度O(logN)。
《用数组实现静态顺序查找二分查找》上有1条评论
评论已关闭。