查找
程序员文章站
2022-07-12 09:10:48
...
查找
顺序表查找
顺序表查找的算法大家公认的最简单的就是下面这种查找了,我想只要写过代码的应该都知道怎么写了 哈哈哈
int Sequential_Search(int *a, int n, int key) {
int i;
for (i = 1; i <= n; i ++) {
if (a[i] = key)
return i;
}
return 0;
}
同学们会疑惑为什么 “i” 从 “1” 开始遍历,因为 “0” 我们要做错误输出呀。。。
那么我们根据这个算法我们给他稍微的改进一下,看官们看好了。
int Sequential_Search2(int *a, int n, int key) {
int i;
a[0] = key;
i = n;
while(a[i] != key) {
i --;
}
return i;
}
这里一样的 “0” 代表查找失败,但是这样写的好处什么是呢?好处就是我不用疯狂的去判断 “i < n” ,看官们想明白了么?
有序表的查找
顺序表的查找看完了之后,看官们就可以随我看看有序表的查找。所谓的有序表,就是有大小的顺序,我们下面的有序表默认的都是按照从大到小排序的,如果各位看官觉得排序算法还是需要给大家科普一下的话,那么出门请右转。
二分查找(折半查找)
但是我看到这个折半查找的时候就觉得特别的蛋疼,好好地二分非要教程折半查找,真是呵呵哒。
所谓二分查找么,顾名思义了,每次都取中间的数据来查找看看对不对嘛。各位有想过跟顺序表查找的遍历有什么好处呢?
int Binary_Search(int *a, int n, int key) {
int low, high, mid;
low = 1;
high = n;
while (low <= high) {
mid = (low + high) / 2;
if (key < a[mid])
high = mid - 1;
else if (key > a[mid])
low = mid + 1;
else
return mid;
}
return 0;
}
二分查找的中值公式是什么呢?
mid = (low + high) / 2
差值查找
差值查找这个东西呢,按照我的理解就是一个不规范的二分查找。或者说二分查找是一个特殊的差值查找。我们怎么理解这个差值查找呢?看官不要急?我先把差值查找的公式给大家列一下
mid = low + (key - a[low]) / (a[high] - a[low]) * (high - low)
然后很多人会大骂一句,我曹,什么鬼。那是因为我markdown用的不熟,其实是我懒得去查数学公式怎么列,哈哈。
实际上,我们看前面的 二分查找的公式,是不是可以改写成这样
mid = low + 1 / 2 *(high - low)