顺序表的顺序查找&&单链表的顺序查找
//顺序表的顺序查找
template<typename T>
bool SeqSearch(T a[], int n, T target) {for (int i = 0; i < n; i++){if (a[i] == target)return true;}return false;
}//单链表的顺序查找
template<typename T>
class Node {
public:T data;Node* next;
};template<typename T>
bool LinkSeqSearch(Node<T>* head, T target) {Node<T>* p = head->next;while (p && p->data != target)p = p->next;if (p != nullptr)return true;return false;
}
折半查找
折半查找的精髓就是控制区间的缩小，需要注意的是我的递归做法中区间是左闭右闭的，而非递归方法中区间是左闭右开的，需要注意的是折半查找对数组的要求是有序的。
//折半查找的递归算法
template<typename T>
void recursive(T a[], int left, int right, T target, bool& flag) {if (left > right || flag == true) return;//递归结束条件int mid = (left + right) / 2;if (target < a[mid])recursive(a, left, mid - 1, target, flag);else if (target > a[mid])recursive(a, mid + 1, right, target, flag);else if (target == a[mid])flag = true;
}template<typename T>
bool BinarySearch1(T a[], int n, T target) {bool res = false;int left = 0, right = n, mid = (left + right) / 2;recursive<T>(a, left, right, target, res);return res;
}//折半查找的非递归算法
template<typename T>
bool BinarySearch2(T a[], int n, T target) {bool res = false;int left = 0, right = n, mid = (left + right) / 2;while (left < right){if (target < a[mid]){right = mid;mid = (left + right) / 2;}else if (target > a[mid]){left = mid + 1;mid = (left + right) / 2;}else if (target == a[mid]){res = true;break;}}return res;
}
全部代码
BasicSearch.h
#pragma once
#ifndef BASICSEARCH_H
#define BASICSEARCH_H
#include<iostream>
using std::cout;
using std::endl;//顺序表的顺序查找
template<typename T>
bool SeqSearch(T a[], int n, T target) {for (int i = 0; i < n; i++){if (a[i] == target)return true;}return false;
}//单链表的顺序查找
template<typename T>
class Node {
public:T data;Node* next;
};template<typename T>
bool LinkSeqSearch(Node<T>* head, T target) {Node<T>* p = head->next;while (p && p->data != target)p = p->next;if (p != nullptr)return true;return false;
}//折半查找的递归算法
template<typename T>
void recursive(T a[], int left, int right, T target, bool& flag) {if (left > right || flag == true) return;//递归结束条件int mid = (left + right) / 2;if (target < a[mid])recursive(a, left, mid - 1, target, flag);else if (target > a[mid])recursive(a, mid + 1, right, target, flag);else if (target == a[mid])flag = true;
}template<typename T>
bool BinarySearch1(T a[], int n, T target) {bool res = false;int left = 0, right = n, mid = (left + right) / 2;recursive<T>(a, left, right, target, res);return res;
}//折半查找的非递归算法
template<typename T>
bool BinarySearch2(T a[], int n, T target) {bool res = false;int left = 0, right = n, mid = (left + right) / 2;while (left < right){if (target < a[mid]){right = mid;mid = (left + right) / 2;}else if (target > a[mid]){left = mid + 1;mid = (left + right) / 2;}else if (target == a[mid]){res = true;break;}}return res;
}#endif // !BASICSEARCH_H
SearchHelper.h
#pragma once
#ifndef SEARCHHELPER_H
#define SEARCHHELPER_H#include<iostream>
#include<ctime>
#include<cassert>
using namespace std;namespace SortTestHelper {//生成n个元素的随机数组int* generateRandomArray(int n, int rangeL, int rangeR) {assert(rangeL < rangeR);int* arr = new int[n];srand(time(NULL));//生成随机种子for (int i = 0; i < n; i++)arr[i] = rand() % (rangeR - rangeL + 1) + rangeL;//rand()返回的是一个随机数 return arr;}template<typename T>void testSearch(string searchName, bool(*search)(T[], int, T), T arr[], int n, T target) {//测试不同查找所耗的时间clock_t start_time = clock();search(arr, n, target);clock_t end_time = clock();cout << searchName << ":" << double(end_time - start_time) / CLOCKS_PER_SEC << endl;}
}#endif // !SEARCHHELPER_H
main.cpp
#include"BasicSearch.h"
#include"SearchHelper.h"int main()
{int* a = SortTestHelper::generateRandomArray(1000001, 1, 1000001);a[1000000] = 1000022;SortTestHelper::testSearch<int>("SeqSearch", SeqSearch<int>, a, 1000001,1000222);int b[] = { 1,2,4,6,7,8,9,10,23,32,35,37,38,45,48,50,60,70,112,234,565,4552 };int n = sizeof(b) / sizeof(int);cout << BinarySearch1<int>(b, n, 0) << endl;cout << BinarySearch2<int>(b, n, 0) << endl;delete []a;return 1;
}