[C++] Các thuật toán tìm kiếm cơ bản thường sử dụng

💚8136💚 · 08/03/2012 10:56

Thuật toán tìm kiếm tuyến tính (linear search)

Mã: Chọn tất cả: #include <iostream> using namespace std; int LinearSearch(int A[], int n, int x) { for (int i = 0; i < n; i++) if (A[i] == x) return i; return -1; // duyệt hết mảng, không tìm thấy x } int main() { int arr[] {32,71,12,45,-26,80,53,-33,7,99,-5,1,2,3,100}; int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang cout << "So luong phan tu trong mang: " << n << endl; cout << LinearSearch(arr, n, -5); return 0; }

💚8136💚 · 08/03/2012 10:56

Thuật toán tìm kiếm nhị phân (binary search) (code này chỉ áp dụng cho mảng đã sắp xếp tăng dần)

Mã: Chọn tất cả: #include <iostream> using namespace std; int BinarySearch(int A[], int n, int x) { int left = 0; int right = n - 1; int mid; while (left <= right) { mid = (left + right) / 2; if (A[mid] == x) return mid; // tìm thấy x, trả về mid là vị trí của x trong mảng A if (A[mid] > x) right = mid - 1; // Giới hạn khoảng tìm kiếm lại là nửa khoảng trước else if (A[mid] < x) left = mid + 1; // Giới hạn khoảng tìm kiếm lại là nửa khoảng sau } return -1; // không tìm thấy x } int main() { int arr[] {-33,-26,-5,1,2,3,7,12,32,45,53,71,80,99,100}; int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang cout << "So luong phan tu trong mang: " << n << endl; cout << BinarySearch(arr, n, -5); return 0; }

💚8136💚 · 08/03/2012 10:56

Thuật toán tìm kiếm nội suy (interpolation search) (code này chỉ áp dụng cho mảng đã sắp xếp tăng dần)

Mã: Chọn tất cả: #include <iostream> using namespace std; int InterpolationSearch(int A[], int n, int x) { int left = 0; int right = n - 1; int mid; while (left <= right && x >= A[left] && x <= A[right]) { mid = left + (right - left) * (x - A[left]) / (A[right] - A[left]); if (A[mid] == x) return mid; if (A[mid] > x) right = mid - 1; else if (A[mid] < x) left = mid + 1; } return -1; // Không tìm thấy x } int main() { int arr[] {-33,-26,-5,1,2,3,7,12,32,45,53,71,80,99,100}; int n = sizeof(arr) / sizeof(arr[0]); // so luong phan tu trong mang cout << "So luong phan tu trong mang: " << n << endl; cout << InterpolationSearch(arr, n, -5); return 0; }