3.查找算法：顺序查找和二分查找

查找

查找，是指在一些数据元素中，通过一定的方法找出与给定关键字相同的数据元素的过程。

列表查找（线性表查找）：从列表中查找指定元素

输入：列表，待查找元素

输出：元素下标（未查找到元素时返回-1）

顺序查找（线性查找）

1. 顺序查找（linear search）

也叫线性查找（linear search），从列表的第一个元素开始，顺序的进行查找，直到找到元素或搜索到列表的最后一个元素为止。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define ARR_SIZE 10int linear_search(const int *arr, const int n, const int val)
{for (int i = 0; i < n; i++){if (arr[i] == val)return i;}return -1;
}int main(int argc, char *argv[])
{srand(time(NULL));int arr[ARR_SIZE] = {0};printf("arr = "); for (int i = 0; i < ARR_SIZE; i++){arr[i] = rand()%10 + 1;printf("%d ", arr[i]);}printf("\n");int val = rand()%10 + 1;printf("search val = %d\n", val);int index = linear_search(arr, ARR_SIZE, val);printf("index = %d\n", index);return 0;
}

结果：

2. 时间复杂度：O(n)

顺序查找算法最差的情况，需要循环n次，所以该算法的时间复杂度为O(n)

二分查找法

1. 二分查找法（binary）

又叫折半查找，从有序的列表初始选区[0 n-1]开始，即下标left = 0，right = n - 1，通过待查找的值与候选区中间（即下标为mid）的值继续比较。可以使候选区减少一半。

代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>#define ARR_SIZE 10int binary_search(const int *arr, const int n, const int val)
{int left = 0;int right = n-1;int mid;while (left <= right){mid = (left + right)/2;if (arr[mid] == val)  return mid;else if (arr[mid] > val) //候选区在leftright = mid - 1;else //候选区在rightleft = mid + 1;}return -1;
}int main(int argc, char *argv[])
{srand(time(NULL));int arr[ARR_SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};printf("arr = "); for (int i = 0; i < ARR_SIZE; i++)printf("%d ", arr[i]);printf("\n");int val = rand()%10 + 1;printf("search val = %d\n", val);int index = binary_search(arr, ARR_SIZE, val);printf("index = %d\n", index);return 0;
}

结果：

2. 时间复杂度：，或logn

二分查找算法，每次执行可以使候选区减少一半，所以时间复杂度为：或logn

顺序查找和二分查找比较

通过以上分析，顺序查找的算法时间复杂度为：O(n),二分查找的算法时间复杂度为：

1. 如果需要查找时，并且被查找的列表有序，那么选择二分查找，执行效率会比顺序查找快很多。

2. 如果需要查找时，被查找的列表无序，就选择顺序查找。但是，如果需要频繁查找时，我们可以选择先对被查找的列表进行排序，然后在选择二分查找，从而提高查找的效率。

ending😃