Linux C语言高级编程数据结构之查找！线性查找与二分查找！

简 介

本章主要介绍一下数据结构中最常见的查找，线性查找和二分查找及其使用代码示例。

线性查找

线性查找，又称为顺序查找，是指在所有给定的值中从一端开始逐个检查每个元素是否为要查找的对象，直到找到为止的过程。

线性查找的过程比较简单，代码演示如下：

//线性查找实现（遍历一遍数组查找到相关元素）

#include

typedef char Data;

//ts是要查找的数组，n是数组中元素的个数，d是要查找的对象

int search(Data *ts, int n, const Data d)

{

for (int i = 0; i < n; i++)

if (ts[i] == d)

return i;

return -1;

}

int main()

{

//开始测试

char cs[6] = {'*','A','B','C','D','E'};

printf("%d\n", mySearch(cs, 6, '*'));

printf("%d\n", mySearch(cs, 6, 'C'));

}

二分查找

二分查找算法，又称折半搜索、二分搜索，是一种在有序数组中查找某一特定元素的搜索算法。

二分查找的过程：

1、首先，要求待查找的数组是排好序的数组，我们假设数组是升序的，即从小到大排序。

2、然后，将要查找的元素与数组的中间元素相对比，如果相等，则表示要查找的元素被找到了，并停止查找；如果要查找的元素小于数组的中间元素，则从数组中间元素开始到数组最后的元素都大于要查找的元素，也就不需要在这里查找了，只需要在数组中间元素到数组第一个元素之间查找；如果要查找的元素大于数组的中间元素，则从数组中间元素到数组第一个元素都小于要查找的元素，也就不需要在其中查找了，只需要在数组中间元素到数组最后的元素之间查找。

3、因此，二分查找算法在查找的过程中只需对比一次，就可以使待查找的对象个数减少一半。查找速度非常快，所以二分查找算法得到了广泛的应用。

二分查找代码实现如下：

//二分查找实现

#include

typedef char Data;

/*while (L

至少为1。当这个循环条件为假时，则表示待查找范围内的数组元素个数已经为0，

即没有可查找的对象*/

int search(Data *ts, int n, const Data d) {

int L = 0;

int R = n - 1;

while (L

int M = (L + R)/2;

if (ts[M] == d)

return M;

if (ts[M] < d)

L = M+1;

else

R = M - 1;

}

return -1;

}

int main()

{

char cs[6] = {'*','A','B','C','D','E'};

printf("%d\n", search(cs, 6, '*'));

printf("%d\n", search(cs, 6, 'C'));

}

这里线性查找和二分查找虽然看起来很简单，但是在实际的项目中这种简单的思路是非常实用的，而且当一个多模块的大型项目出现问题不好排查时二分查找的思路也是一个比较有效的方式。因此，学习编程的过程中，这种思路以及思维方式的积累还是很重要的，希望大家在平时的学习中多多思考、多多积累。