Các Giải Thuật Tìm Kiếm - Searching Algorithms

Tìm kiếm cơ bản và nâng cao với các giải thuật, được hiện thực bằng ngôn ngữ C++.

Tìm kiếm tuần tự vét cạn - Sequential search

Giải thuật tìm kiếm cơ bản nhất, tìm từ đầu cho đến cuối.

123456789101112131415161718192021222324252627
#include <iostream> using namespace std; #define N 100000 int numberOfElements, key; int arr[N]; int sequentialSearch(int arr[], int numberOfElements, int key) { int index = 0; while(index < numberOfElements) { if (arr[index] == key) return index; index++; } } int main() { cin >> numberOfElements; for (int index = 0; index < numberOfElements; index++) cin >> arr[index]; cin >> key; cout << linearSentinelSearch(arr, numberOfElements, key); return 0; }

Sắp xếp nhanh - Quick sort

Hàm hỗ trợ sắp xếp (khi cần) cho các giải thuật tìm kiếm.

1234567891011121314151617181920
void quickSort(int arr[], int left, int right) { if (left >= right) return; int L = left, R = right; int x = arr[(L + R) / 2]; while (L < R) { while (arr[L] < x) L++; while (arr[R] > x) R--; if (L <= R) { swap(arr[L], arr[R]); L++; R--; } } quickSort(arr, left, R); quickSort(arr, L, right); }

Tìm kiếm nhị phân - Binary search

Tìm kiếm nhị phân chỉ có ý nghĩa khi dữ liệu đã được sắp xếp, do đó ta hiện thực thêm hàm quickSort để sắp xếp dữ liệu trước.

123456789101112131415161718192021222324252627282930313233343536373839
#include <iostream> using namespace std; #define N 100000 int numberOfElements, key; int arr[N]; int binarySearch(int arr[], int numberOfElements, int key) { int left = 0, right = numberOfElements - 1; while (left <= right) { int mid = (left + right) / 2; if (arr[mid] == key) return mid; if (arr[mid] > key) right = mid - 1; else left = mid + 1; } return -1; } int main() { cin >> numberOfElements; for (int index = 0; index < numberOfElements; index++) cin >> arr[index]; cin >> key; quickSort(arr, 0, numberOfElements - 1); for (int index = 0; index < numberOfElements; index++) cout << arr[index] << " "; cout << endl << binarySearch(arr, numberOfElements, key); return 0; }

Tìm kiếm tuần tự lính canh - Linear sentinel search

12345678910111213141516171819202122232425262728
#include <iostream> using namespace std; #define N 100000 int numberOfElements, key; int arr[N]; int linearSentinelSearch(int arr[], int numberOfElements, int key) { arr[numberOfElements] = key; int index = 0; while(true) { if (arr[index] == key) return index; index++; } } int main() { cin >> numberOfElements; for (int index = 0; index < numberOfElements; index++) cin >> arr[index]; cin >> key; cout << linearSentinelSearch(arr, numberOfElements, key); return 0; }

Tìm kiếm nội suy - Interpolation search

Cần sắp xếp dữ liệu trước khi tìm kiếm hoặc dữ liệu đã được sắp xếp sẵn.

123456789101112131415161718192021222324252627282930313233343536373839
#include <iostream> using namespace std; #define N 100000 int numberOfElements, key; int arr[N]; int interpolationSearch(int arr[], int numberOfElements, int key) { int left = 0, right = numberOfElements - 1; while (left != right && arr[left] != arr[right]) { int mid = left + ((right - left) / (arr[right] - arr[left])) * (key - arr[left]); if (arr[mid] == key) return mid; if (arr[mid] > key) right = mid - 1; else left = mid + 1; } return -1; } int main() { cin >> numberOfElements; for (int index = 0; index < numberOfElements; index++) cin >> arr[index]; cin >> key; quicksort(arr, 0, numberOfElements - 1); for (int index = 0; index < numberOfElements; index++) cout << arr[index] << " "; cout << endl << interpolationSearch(arr, numberOfElements, key); return 0; }