算法-查找算法(顺序查找二分查找)

3.查找算法

查找也称为搜索，就是从数据中找出满足特定条件的元素。

常见的查找算法：顺序查找、二分查找。

3.1 顺序查找算法

顺序查找算法又称为线性查找，是一种比较简单的查找算法，是将数据一项一项的按照顺序逐个查找，它的缺点是效率低下。

顺序查找过程：

从表中的最后一个记录开始，逐个进行记录的关键字与给定值进行比较，若某个记录的关键字与给定值相等，则查找成功，找到所查的记录；反之，若直到第一个记录，其关键字和给定值比较都不相等，则表明表中没有所查的记录，查找失败。

#include <iostream>
using namespace std;//顺序查找算法，时间复杂度为O(n)
int seqSearch(int arr[], int value, int n)
{for (int i = 0; i < n; i++){if (arr[i] == value){return i;}}return -1;
}int main()
{int arr[] = {  2, 3, 5, 6, 7, 8, 10, 12, 13, 14, 17, 18 };int length = sizeof(arr) / sizeof(arr[0]);cout << seqSearch(arr, 8, length) << endl;return 0;
}

3.2 二分查找算法

二分查找也称为折半查找（Binary Search），它是一种高效的查找算法。

二分查找过程如下：

将待排序的n个元素分成大致相同的两半，取a[mid]和待查找的x做比较，如果x==a[mid]，则找到了x，算法结束；如果x<a[mid],则外卖需要在数组a的左半部分继续搜索x；如果x>a[mid],则我们需要再数组a的右半部分继续搜索x。

二分查找算法实现的前提条件：

二分查找针对的数据必须是有序的，如果无序，需要先排序，所以，二分查找适合用在插入删除操作不频繁，一次排序多次查找的场景。

二分查找一般只用在通过顺序存储结构实现的序列中，因为顺序存储结构（数组）按下标随机访问数据元素的时间复杂度为O(1),而链表实现随机访问元素的时间复杂度为O(n),如果用链表存储，二分查找的时间复杂度就会变很高，得不偿失。

#include <iostream>
using namespace std;//二分查找算法，时间复杂度为O(logn)，递归
int binarySearch(int arr[], int left, int right, int target)
{int mid = (left + right) / 2;if (left > right){return -1;}if (arr[mid] == target){return mid;}else if (arr[mid] > target){return binarySearch(arr, left, mid - 1, target);}else{return binarySearch(arr, mid + 1, right, target);}}//二分查找算法，时间复杂度为O(logn),非递归
int binarySearch_non_recursive(int arr[],  int target, int n)
{int left = 0 , right = n - 1,mid = 0;while (left <= right){mid = (left + right) / 2;if (arr[mid] == target){return mid;}else if (arr[mid] > target){right = mid - 1;}else if (arr[mid] < target){left = mid + 1;}}return -1;
}int main()
{int arr[] = { 2, 3, 5, 6, 7, 8, 10, 12, 13, 14, 17, 18 };int length = sizeof(arr) / sizeof(arr[0]);//cout << binarySearch(arr, 0, length - 1, 5) << endl;cout << binarySearch_non_recursive(arr, 18, length) << endl;return 0;
}