顺序查找算法
顺序查找是非常简单常用的查找算法，基本思路：从第一个元素m开始逐个与需要查找的元素x进行比较，当比较到元素值相同(即m=x)时返回元素m的下标，如果比较到最后都没有找到，则返回-1。该算法的时间复杂度为O(n)，如果数据量很大时查找效率会很低。
1 #include<stdio.h> 2 3 /* 顺序查找算法 4 a为数据数组,len为数组a的长度，x为查找的元素
5 如果查找成功返回元素x在数组a中的下标，找不到则返回-1
6 */ 7 int search(int a[],int len, int x) 8 { 9 int i;10 for (i=0; i<len; i++)11 {12 if(x==a[i])
13 return i; // 返回元素的下标 14 }15 return -1; // 没有找到 16 }17 18 int main()19 {20 int a[10]={1,3,5,2,0,9,8,4,7,6};21 int x=2; // 需要查找的元素22 int i = search(a, 10, x);23 if(i!=-1)24 printf("元素%d在第%d个位置n",x,i+1);25 else26 printf("没有找到元素:%dn",x);27 return 0;28 }
二分查找算法
二分查找（又称为折半查找）是在有序序列中查找比较多的查找算法，基本思路：设有一个从小到大的序列，取中间的元素m进行比较，如果等于需要查找的元素x则返回元素m的下标，若x大于m则再从右边的区间查找，若x小于m则再从左边的区间查找，这样每次减少一半的查找范围。时间复杂度为O(lgn)，查找速度相对顺序查找要快很多，但是查找的数据序列必须是有序序列（即数据是从小到大或从大到小排序的）。
1 #include<stdio.h> 2 3 /* 二分查找算法
4 a为数据数组,len为数组a的长度，x为查找的元素
5 如果查找成功返回元素x在数组a中的下标，找不到则返回-1
6 */ 7 int binarySearch(int a[],int len, int x) 8 { 9 int mid; // 中间下标10 int low=0; // 区间的左端下标11 int high=len-1; // 区间的右端下标12 13 while(low <= high)14 {15 mid = low + (high-low)/2; // 计算中间下标， 若使用(low+high)/2可能会有整数溢出：当low和high的值较大时(接近整型数所能表示的范围),low+high的值就会溢出16 if(x==a[mid])17 return mid; // 若找到返回元素的下标 18 else if(x>a[mid])19 low=mid+1; // 在右半边区间搜索 20 else21 high=mid-1; // 在左半边区间搜索 22 }23 return -1; // 没有找到 24 }25 26 int main()27 {28 int a[10]={0,1,2,3,4,5,6,7,8,9}; // 必须是有序序列 29 int x=7; // 需要查找的元素30 int i = binarySearch(a, 10, x);31 if(i!=-1)32 printf("元素%d在第%d个位置n",x,i+1);33 else34 printf("没有找到元素:%dn",x);35 return 0;36 }
