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ã:#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;
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ã:#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;