C语言数据结构之查找（顺序查找，折半查找）
tips：前些天已经学习了树和图的相关知识，今天来总结下两种常用的查找方式（顺序查找，折半查找）。
为了演示方便，顺序查找和折半查找的数据存储结构就直接采用数组。
1、顺序查找
顺序查找又称线性查找，主要用于在线性表中进行查找；
顺序查找跟我们用循环遍历进行暴力破解类似。。
直接看代码：
#define N 11//顺序查找（适用于线性表）
int Seq_Search(int *arr, int key)
{int i;arr[0] = key;//0号下标作为哨兵for (i = N-1; arr[i] != key; i--);return i;
}
对，顺序查找就是这么简单。。。
2、折半查找（二分查找）
折半查找仅适用于有序的顺序表
思路：
- 将给定值key与中间元素的关键字对比；
- 若相等，则直接返回该元素的位置；
- 若不等，则在前半部分或者后半部分进行查找；
具体实现：
//折半查找（二分查找），适用于有序的顺序表
int Binary_Search(int *arr, int key)
{int low = 1;//元素起始下标int high = N-1;//最后元素下标int mid;//中间元素下标while (low <= high){mid = (low + high) / 2;if (arr[mid] == key)return mid;//查找成功else if (arr[mid] > key)high = mid - 1;//查找前半部分elselow = mid + 1;//查找后半部分}return -1;//查找失败
}
注意这里循环的终止条件是low<=high;
接下来，我们可以在main()函数中测试一下：
int main()
{//数组的0号下标不存放实际意义key（可以声明时存放数组长度）int arr1[N] = { N,1,4,2,7,5,6,9,8,3,0 };if (Seq_Search(arr1, 4) != 0)printf("4元素下标为：%d\n", Seq_Search(arr1, 4));elseprintf("该元素不存在！\n");int arr2[N] = { N,0,1,2,3,4,5,6,7,8,9 };if (Binary_Search(arr2, 4) != -1)printf("4元素下标为：%d\n", Binary_Search(arr2, 4));elseprintf("该元素不存在！\n");return 0;
}
测试结果：
积一时之跬步，臻千里之遥程。
